记录编号	601353	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4083.猴猴的比赛	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	1.284 s
提交时间	2025-06-16 20:42:39	内存使用	4.60 MiB

#include <iostream>
using namespace std;
const int N=1e5+5;
int n;
struct tree{
    int head[N],nxt[N],to[N];
    int num=0;
    void add(int x,int y){
        num++;
        to[num]=y;
        nxt[num]=head[x];
        head[x]=num;
    }
};
tree t1,t2;
int in[N],out[N],num=0;
void dfs(int x){
    in[x]=++num;
    for(int i=t1.head[x];i;i=t1.nxt[i]){
        dfs(t1.to[i]);
    }
    out[x]=++num;
}

int tr[N*2];
int lb(int x){
    return x&(-x);
}
void add(int x,int y){
    for(int i=x;i<=num;i+=lb(i)){
        tr[i]+=y;
    }
}
int q(int x){
    int ans=0;
    for(int i=x;i>0;i-=lb(i)){
        ans+=tr[i];
    }
    return ans;
}
int ans=0;
void dfss(int x){
    add(in[x],1);
    add(out[x],-1);
    ans+=q(in[x]-1);
    for(int i=t2.head[x];i;i=t2.nxt[i]){
        dfss(t2.to[i]);
    }
    add(in[x],-1);
    add(out[x],1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        t1.add(x,y);
    }
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        t2.add(x,y);
    }
    dfs(1);
    dfss(1);
    cout<<ans;
    return 0;
}