1681 공공 조상

1681 공공 조상
Description
거대 한 가족 이 있 습 니 다. 모두 n 명 입 니 다.이 n 명의 조상 관 계 는 마침 나무 모양 의 구 조 를 형성 한 것 으로 알려 져 있다.
또 다른 미 지 의 평행 우주 에서 이 n 명의 조상 관 계 는 아직도 나무 구조 이지 만 그들 은 서로 간 의 관 계 는 완전히 다르다. 원래 의 조상 은 후대 가 되 었 고 후손 은 또래 가 되 었 을 것 이다.
두 사람의 친밀 도 는 이 두 평행 우주 에서 얼마나 많은 사람들 이 그들의 공공 조상 이 었 는 지 정의 한다.
전체 가족의 친밀 도 는 임의의 두 사람의 친밀 도의 총화 로 정의 된다.
Input
첫 번 째 줄 의 개수 n (1 < = n < = 100000)
다음 n - 1 줄 마다 두 개의 수 x, y 는 첫 번 째 평행 우주 x 가 y 의 아버지 라 는 것 을 나타 낸다.
다음 n - 1 줄 마다 두 개의 수 x, y 는 두 번 째 평행 우주 x 가 y 의 아버지 라 는 것 을 나타 낸다.
Output
한 수 는 온 가족의 친밀 도 를 나타 낸다.
Input example
5 1 3 3 5 5 4 4 2 1 2 1 3 3 4 1 5
Output example
6
Solution
신기 한 데이터 구조 문제 입 니 다. 먼저, 우 리 는 dfs 에서 첫 번 째 나 무 를 겪 고 각 점 의 시간 스탬프 와 시간 스탬프 (이 점 은 tarjan 과 유사 합 니 다) 를 기록 합 니 다. 두 번 째 나무 에 대해 서도 dfs 를 한 번 진행 합 니 다. 모든 노드 u 에 대해 우 리 는 두 번 째 나무 에 기록 하고 u 라 는 노드 를 포함 하지 않 을 때 몇 개의 노드 가 u 에 포 함 된 시간 스탬프 에 나타 난 적 이 있 습 니까?나 타 났 기 때문에 이 점 이 덮 인 시간 스탬프 는 u 를 조상 으로 하 는 것 이 아니 라 는 것 을 알 수 있 습 니 다. 그 후에 우 리 는 두 번 째 나무 에서 u 의 자 나 무 를 겪 었 습 니 다. 그리고 역 사 를 끝 낸 후에 몇 개의 노드 가 u 에 포 함 된 시간 스탬프 에 나 타 났 는 지 다시 통계 합 니 다. 두 번 의 답 이 서로 줄 어 든 것 은 바로 두 개의 나무 에서 u 를 조상 으로 하 는 노드 수 입 니 다. 이 차 이 를 sum 으로 설정 합 니 다.이 노드 u 가 답 에 기여 한 것 은 (sum - 1) * (sum - 2) 입 니 다. u 에 포 함 된 시간 스탬프 의 결점 개 수 를 통계 할 때 우 리 는 트 리 배열 로 유지 할 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.

#include
#include
#include
#include
using namespace std;
vector <int> edge[100010];
vector <int> pic[100010];
long long tree[10000000];
struct node{
    int in,out;
}dfn[100010];
int cnt,In[100010],n;
long long ans;
int lowbit(int x){
    return x&(-x);
}
void dfs1(int u,int fa){
    dfn[u].in=++cnt;
    for (int i=0;iint v=edge[u][i];
        if (v==fa) continue;
        dfs1(v,u);
    }
    dfn[u].out=cnt;
}
long long query(int x){
    long long ans=0;
    for (int i=x;i;i-=lowbit(i)){
        ans+=tree[i];
    }
    return ans;
}
void add(int x,int val){
    for (int i=x;i<=n;i+=lowbit(i)){
        tree[i]+=val;
    } 
}
void dfs2(int u,int fa){
    long long sum=query(dfn[u].out)-query(dfn[u].in-1);
    add(dfn[u].in,1);
    for (int i=0;iint v=pic[u][i];
        if (v==fa) continue;
        dfs2(v,u);
    }
    sum=query(dfn[u].out)-query(dfn[u].in-1)-sum-1;
    ans+=(sum-1)*sum/2;
}
int main(){
    scanf("%d",&n);
    for (int i=1;iint u,v;
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        In[v]++;
    }
    for (int i=1;i<=n;i++)
        if (!In[i]) dfs1(i,-1);
    memset(In,0,sizeof(In));
    for (int i=1;iint u,v;
        scanf("%d%d",&u,&v);
        pic[u].push_back(v);
        In[v]++;
    }
    for (int i=1;i<=n;i++)
        if (!In[i]) dfs2(i,-1);
    printf("%lld
",ans);
    return 0;
}