| 比赛 | 
    树状数组练习 | 
    评测结果 | 
    AAAAAAAAAAAAAAAAAAAA | 
    | 题目名称 | 
    猴猴的比赛 | 
    最终得分 | 
    100 | 
    | 用户昵称 | 
    zjzhe | 
    运行时间 | 
    1.453 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    10.87 MiB  | 
    | 提交时间 | 
    2025-06-12 15:54:20 | 
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,val[N],dfn[N],low[N],dn,ans;
vector<int>lk[N],lk2[N];
void add(int x,int v){for(;x<=n;x+=x&-x)val[x]+=v;}
int query(int x){
	int res=0;
	for(;x;x-=x&-x)res+=val[x];
	return res;
}
void dfs2(int u,int f){
	dfn[u]=++dn;
	for(int v:lk2[u]){
		if(v==f)continue;
		dfs2(v,u);
	}
	low[u]=dn;
}
void dfs(int u,int f){
	for(int v:lk[u]){
		if(v==f)continue;
		ans-=query(low[v])-query(dfn[v]-1);
		dfs(v,u);
		ans+=query(low[v])-query(dfn[v]-1);
	}
	add(dfn[u],1);
} 
int main(){
	freopen("monkeyclim.in","r",stdin);
	freopen("monkeyclim.out","w",stdout);
	cin>>n;
	for(int i=1,a,b;i<n;i++)cin>>a>>b,lk[a].push_back(b),lk[b].push_back(a);
	for(int i=1,a,b;i<n;i++)cin>>a>>b,lk2[a].push_back(b),lk2[b].push_back(a);
	dfs2(1,0),dfs(1,0);
	cout<<ans;
	return 0;
}