比赛 20241128 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 猴猴的比赛 最终得分 100
用户昵称 徐诗畅 运行时间 0.589 s
代码语言 C++ 内存使用 5.24 MiB
提交时间 2024-11-28 10:39:58
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int cnt1,cnt2,head1[N],head2[N],n,ans;
struct edge{
	int v,next;
}e1[N],e2[N];
int dfn[N],siz[N],c[N];
void add(int x,int y){for(;x<=n;x+=x&-x) c[x]+=y;}
int ask(int x){int y=0;for(;x;x-=x&-x) y+=c[x]; return y;}
void addedge1(int u,int v){
	e1[++cnt1].v=v;
	e1[cnt1].next=head1[u];
	head1[u]=cnt1;
}
void addedge2(int u,int v){
	e2[++cnt2].v=v;
	e2[cnt2].next=head2[u];
	head2[u]=cnt2;
}
int num;
void dfs1(int u,int f){
	siz[u]=1; dfn[u]=++num;
	for(int i =head1[u];i;i=e1[i].next){
		int v=e1[i].v;
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int f){
	int flag=0;
	ans-=ask(dfn[u]+siz[u]-1)-ask(dfn[u]);
	for(int i = head2[u];i;i=e2[i].next){
		int v=e2[i].v;
		if(v==f) continue;
		flag=1;
		dfs2(v,u);
		add(dfn[v],1);
	}
	//if(flag) 
	ans+=ask(dfn[u]+siz[u]-1)-ask(dfn[u]); 
//	cout<<u<<" "<<ans<<" "<<ask(dfn[u]+siz[u]-1)-ask(dfn[u])<<endl;
}
int main(){ 
    freopen("monkeyclim.in","r",stdin);
    freopen("monkeyclim.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		addedge1(u,v); addedge1(v,u);
	}
	for(int i = 1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		addedge2(u,v); addedge2(v,u);
	}
	dfs1(1,0); dfs2(1,0);
	printf("%d",ans);
	return 0;
}

/*
7
1 2
2 3
2 4
3 5
3 6
5 7
1 2
2 4
4 5
4 6
1 3
3 7
*/