어린 왕자 (LCA 활용)

제목 링크:https://ac.nowcoder.com/acm/problem/206091 묘사 하 다.
제목 배경 "내 가 이 길 을 따라 쭉 올 라 가면 그 별 을 딸 수 있어 요." "그런데 물리 가 너무 어려워 요." "그럼 저 는 별 을 튀 기 러 갈 게 요." "달 에 올 라 가 벌 서 라 도 괜찮아 요."그 는 베란다 에 서서 옆방 에서 훔 쳐 온 딸기 맛 막대 사탕 을 입 에 물고 눈 을 가 늘 게 뜨 고 날 리 는 눈 속 에서 가을 냄새 를 맡 으 려 했다.흑 과 백 은 분명 하지 않 은 경 계 를 이 루 며 낯 선 모양 을 혼돈 하 게 그 려 낸다.흩 어 진 선 같 기도 하고.그 는 또 눈 을 가 늘 게 뜨 고 그 으스스 한 밤하늘 을 보고 있다.그 많은 별 들 처럼.남 은 막대 기 를 던 지 는 김 에 그 는 하품 을 하 며 주방 의 '작은 점 에서 이 겨 라' 를 떠 올 렸 다.다시 보면 N 개의 별 이 N - 1 개의 선 을 잡 고 있다.N - 1 개의 하 얀 선 이 N 개의 별 을 묶 어 하나의 성단 으로 묶 어 놓 은 것 이다."당신 은 왜 이렇게 오랫동안 별 을 쳐 다 보 았 습 니까?" "나 는 작은 별 을 좋아 하기 때문에 별 을 바라 보 며 뇌 로 우주 에 신 호 를 보 내 려 고 했 습 니 다." "그럼 우 주 는 당신 에 게 피드백 을 주 었 습 니까?" "아 닙 니 다." "그 작은 별 이 우주 가 오기 전에 내 앞 에 먼저 달 려 왔 으 면 좋 겠 습 니 다." "그럼 하 나 를 바 꾸 세 요. 하늘의 별 이 훨씬 많 습 니 다."- 그런데 그 선 이 너무 적어 요. -그럼 좀 많 으 면 좋 겠 다.그래서 그 는 M 개의 검은색 선과 N - 1 개의 흰색 선 이 교차 하 는 것 을 희미하게 보 았 고 겹 치지 도 않 고 얽 히 지도 않 았 다.별 들 을 가볍게 끌 고 묶 지 는 않 았 지만 어찌 된 일 인지 빠 져 나 오지 못 했다."우주 가 너 에 게 피드백 을 주 었 니?" "아니 야." "그럼 바 꿔 봐. 하늘의 별 이 훨씬 많아." "은하계 전 체 를 돌아 다 니 면서 나 는 아마 더 밝 은 별 을 찾 지 못 할 거 야." 그럼 따 러 가자.자신의 별 은 스스로 따다.그러나 나의 우주선 은 유성 을 만 날 수도 있 고 모든 연 료 를 다 쓸 수도 있다.그러나 우주의 신 호 는 그 작은 별 이 다가 오고 있다 는 것 을 보 여 준다.성하 만경, 모두 상 견 례 야.그 는 좀 느 리 잖 아.그럼 튀 겨.그 는 존재 하지 않 는 선과 별 들 을 보고 자신 이 가지 고 있 는 두 발의 미사일 중 한 발 로 흰 선 을 파괴 하여 그 별 들 을 두 부분 으로 나 누 기로 결정 했다.그 가 물리 책 에 "\ # define 별 튀김 은 그 별 들 을 두 부분 으로 나 누 었 다" 고 썼 다.그리고 실 망 스 럽 게 도 가끔 은 별 튀김 에 성공 하지 못 할 때 가 있다 는 것 을 알 게 되 었 다.그래서 그 는 만년 의 행복 을 보장 하 는 미사일 로 검 은 선 을 파괴 하기 로 했다.모든 달 이 우주인 을 만 날 수 있 는 것 은 아니다.그러나 그 는 자신의 작은 별 을 다음 초 에 그의 품 에 나타 나 게 하 는 방안 이 얼마나 되 는 지 알 고 싶 었 다.그런데 그 는 어떤 상 견 례 를 그의 작은 별 에 게 주 려 고 합 니까?그 는 미사일 두 발, '작은 점 에서 이 겨 라' 한 권, '일반 고등학교 과정 표준 실험 교과서 물리 필수 2' 한 권, 딸기 맛 막대 사탕 한 개 만 있 었 다.딸기 맛 막대 사탕 은 이미 그 가 다 먹고 버 렸 고 별 도 물리 책 과 물리 교 부 를 좋아 하지 않 을 것 이다.그래서 그 는 미사일 한 발 에 흰 선 하나 로 그의 작은 별 을 그의 앞 에 데려 다 주 더 라 도 검 은 선 하 나 를 더 터 뜨 려 작은 별 에 게 주기 로 했다.아마도 이렇게 하면 그의 사랑 과 희망 을 조금 더 자라 게 할 것 이다.적어도 조금 은 커 보인다.겸사겸사 방안 수도 그 에 게 작은 별 을 주 었 다.별 이 두 부분 으로 나 뉘 어 져 있다 면 아래 의 별 은 떨 어 질 것 이다.만약 그들 이 그 와 같은 사람 을 만 나 지 않 았 다 면, 그들 은 배 고 픈 작은 괴물 을 만 났 을 것 이다. 작은 괴물 은 이 작은 별 들 을 씹 었 을 것 이다."나 는 하늘 가득 한 별빛 속 에 숨 어 있 잖 아." 그 는 외계인 이 그의 별 들 을 빼 앗 아 가 는 것 을 두려워 하지 않 아.뺏 을 수 없어.
입력
첫 번 째 줄 은 두 개의 정수 N 과 M 을 포함한다.이후 N - 1 줄 은 각 줄 에 두 개의 정수 X 와 Y 를 포함 하여 X 와 Y 사이 에 흰 선 이 있 음 을 나타 낸다.그 다음 에 M 줄 은 각 줄 에 두 개의 정수 X 와 Y 를 포함 하여 X 와 Y 사이 에 검 은 선 이 있다 는 것 을 나타 낸다.
출력
하나의 정 수 를 출력 하 는 것 은 흰 선과 검 은 선 을 폭파 시 켜 별 을 두 부분 으로 나 누 는 방안 수 를 나타 낸다.
제목: N 노드 의 나 무 를 정 하고 N - 1 개의 흰 변 을 통 해 연결 하 며 M 개의 검 은 변 을 연결 합 니 다 (흰 변 과 중복 되 지 않 음). 지금 은 흑백 변 을 각각 파괴 하고 이 나 무 를 두 부분 으로 나 눌 수 있 는 방안 이 몇 가지 가 있 는 지 물 어 봅 니 다.
사고: 처음에 사 이 드 더 블 연결 을 사용 하여 만 들 었 습 니 다. 축 소 된 방안 의 수 는 (사 이 드 더 블 연결 분량 수 - 1) * m (분량 간 의 변 은 반드시 흰색 변 이 고 검 은 변 이 라면 검 은 변 사이 에 반드시 흰색 변 이 있어 야 한 변 의 더 블 연결 분량 을 구성 할 수 있 습 니 다) 입 니 다. 그리고 분량 안의 방안 에 대해 검 은 변 이 있 으 면 방안 의 수 는 이 분량 안의 흰색 변 수 이 고 0 개의 검 은 변 은 흰색 변 수 입 니 다.×흑 변 총수.그러나 이것 은 전면적 이지 않다. 만약 에 한 변 만 자 르 면 두 개의 연결 로 생각 할 수 있다. 그러나 여 기 는 두 개의 변 을 자 르 고 한 변 을 자 른 후에 원래 의 변 을 두 번 연결 하면 반드시 '원래 의 인마' 가 되 는 것 은 아니다.나무의 각도 에서 출발 하여 나무의 임의의 두 점 사이 (흰 변 과 중복 되 지 않 음) 에 검 은 변 (u - > v) 을 추가 하면 (u - > lca (u, v) 의 회로 가 구 성 됩 니 다. 이 회로 의 임의의 점 에서 벗 어 나 려 면 아버지 노드 와 연 결 된 변 과 이 검 은 변 을 차단 해 야 합 니 다.이 를 통 해 알 수 있 듯 이 한 점 이 두 개의 검 은 변 의 영향 을 받 을 때 한 점 만 없 앨 수 있 기 때문에 벗 어 날 수 없다.어떤 것 이 검 은 변 의 영향 을 받 지 않 았 을 때 아버지 노드 와 의 변 을 끊 으 면 벗 어 날 수 있다.LCA 의 구 해 에 대해 서 는 수 사슬 로 나 누 었 다.간단하게 다음 체인 의 부분 을 소개 합 니 다. 한 아버지 노드 의 자 결점 을 두 가지 로 나 누 었 습 니 다. 무 거 운 아들 과 가 벼 운 아들 입 니 다.(하위 노드 가 있 는 하위 나무의 노드 수 에 따라 나 누고 노드 수가 가장 많은 것 은 무 거 운 아들 이다) 한 노드 에 대해 무 거 운 아들 이 많 습 니 다 (최대 치가 여러 개 있 으 면 마음대로 하 나 를 선택 하면 됩 니 다).무 거 운 아들 사이 의 가장 자 리 는 무 거 운 사슬 을 구성 하고, 반대로 가 벼 운 사슬 을 구성한다.무 거 운 체인 의 점 은 체인 의 맨 위로 바로 뛰 어 내 릴 수 있 고 가 벼 운 체인 도 괜 찮 지만 그의 맨 위 는 자신 이다.이것 은 아마도 나무 노드 에 따라 경중 을 나 누 는 아들 의 원인 중 하나 일 것 이다.가능 한 한 많은 점 을 엘리베이터 를 탈 수 있 도록 하여 시간 효율 을 최적화 하 는 목적 을 달성 하도록 한다.lca (u, v) 를 구 할 때 두 개의 체인 꼭대기 의 깊이 에 따라 어느 것 이 위로 뛰 는 지 선택 합 니 다 (체인 꼭대기 가 같 으 면 같은 체인 에 있 으 면 순환 에 들 어가 지 않 음 을 설명 합 니 다). 만약 에 u 가 있 는 체인 꼭대기 의 깊이 가 v 보다 깊 으 면 u 가 있 는 체인 꼭대기 노드 의 부모 노드 로 뛰 어 갑 니 다.왜 체인 꼭대기 의 깊이 에 따라 뛰 는 지 에 대해 제 이 해 는 u, v 가 있 는 두 개의 서로 다른 체인 에 대해 만약 에 체인 꼭대기 의 깊이 가 같다 면 이들 의 lca 는 아직도 체인 꼭대기 위 에 있 고 적어도 체인 꼭대기 의 아버지 노드 이기 때문에 이들 은 마음대로 뛰 면 됩 니 다.(한 번 뛰 면 될 것 같 아 요. 한 번 뛰 고 나 면 새 체인 꼭대기 의 깊이 가 다른 것 보다 얕 을 거 예요. 다음 에는 꼭 다른 점프 일 거 예요. 그런데 프로 그래 밍 이 번 거 로 워 요. 생각 하지 않 고 성실 하 게 하나씩 뛰 어 요.)u 체인 꼭대기 의 깊이 가 깊 으 면 마지막 으로 lca 를 수렴 하기 위해 u 가 뛰 어야 합 니 다. lca 의 위치 에서 고려 할 때 이들 의 lca 는 반드시 u 가 있 는 체인 에 있 지 않 고 체인 꼭대기 위 에 있 기 때문에 u 가 뛰 는 것 이 아니 라 v 는 반드시 u 보다 작 기 때 문 입 니 다. lca 는 v 가 있 는 체인 에 있 을 수 있 기 때문에 반드시 체인 꼭대기 가 깊 게 뛰 는 것 입 니 다. 마지막 까지 뛰 면 두 사람 은 같은 체인 에 있 습 니 다.가 벼 운 체인 과 무 거 운 체인 두 가지 상황 을 고려 합 니 다. 가 벼 운 체인: 한 점 이기 때문에 lca 는 두 가지 가 있 는 점 입 니 다. 무 거 운 체인: u, v 깊이 (뛰 고 난 후에 원래 의 u, v 가 아 닙 니 다) 가 얕 은 것 은 lca 입 니 다.

#include
using namespace std;
const int Ms=2e5+5;
struct Enode
{
    int v,nex;
}E[Ms*2];
struct Tnode
{
    int fa,son,deep,sz,top;
}T[Ms];
int head[Ms],a[Ms],m;
long long ans=0;
void dfs1(int u,int fa)
{
    int mx=0,v;
    T[u].deep=T[fa].deep+1;
    T[u].fa=fa;
    T[u].sz=1;
    for(int i=head[u];i;i=E[i].nex)
    {
        v=E[i].v;
        if(v==fa)continue;
        dfs1(v,u);
        T[u].sz+=T[v].sz;
        if(T[v].sz>=T[mx].sz)mx=v;
    }
    T[u].son=mx;
}
void dfs2(int u,int top)
{
    int v;
    T[u].top=top;
    if(T[u].son)dfs2(T[u].son,top);
    for(int i=head[u];i;i=E[i].nex)
    {
        v=E[i].v;
        if(v==T[u].fa||v==T[u].son)continue;
        dfs2(v,v);
    }
}
int qlca(int x,int y)
{
    int tx=T[x].top,ty=T[y].top;
    while(tx!=ty)
    {
        if(T[tx].deep>=T[ty].deep)
        {
            x=T[tx].fa;
            tx=T[x].top;
        }
        else
        {
            y=T[ty].fa;
            ty=T[y].top;
        }
    }
    return T[x].deep>T[y].deep?y:x;
}
void solve(int u)
{
    int v;
    for(int i=head[u];i;i=E[i].nex)
    {
        v=E[i].v;
        if(v==T[u].fa)continue;
        solve(v);
        a[u]+=a[v];
    }
    if(T[u].fa)//           
    {
        if(a[u]==1)ans++;//       ，        
        else if(a[u]==0)ans+=m;//      ，                  ，          
    }
}
void add_edge(int u,int v)
{
    static int cnt=1;
    E[cnt]=(Enode){v,head[u]};
    head[u]=cnt++;
    E[cnt]=(Enode){u,head[v]};
    head[v]=cnt++;
}
int main()
{
    int n,u,v,ff;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ff=qlca(u,v);
        if(ff!=u)a[u]++,a[ff]--;
        if(ff!=v)a[v]++,a[ff]--;
    }
    solve(1);
    cout<<ans<<endl;
}

무슨 잘못 이 있 으 면 지적 을 환영 합 니 다 ^ ^.