记录编号	597512	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	猴猴的比赛	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.607 s
提交时间	2024-11-28 19:42:28	内存使用	5.94 MiB

#include<bits/stdc++.h>
using namespace std;
int n,a[200010],h1[100010],v1[200010],ne1[200010],tot1,l[100010],r[100010],cnt;
int h2[100010],v2[200010],ne2[200010],tot2;
long long c[200010],ans;
void add1(int x,int y)
{
	tot1++;
	v1[tot1]=y;
	ne1[tot1]=h1[x];
	h1[x]=tot1;
}
void add2(int x,int y)
{
	tot2++;
	v2[tot2]=y;
	ne2[tot2]=h2[x];
	h2[x]=tot2;
}
void dfs1(int x,int fa)
{
	cnt++;
	a[cnt]=x;
	l[x]=cnt;
	for(int i=h1[x];i;i=ne1[i])
	{
		int y=v1[i];
		if(y==fa) continue;
		dfs1(y,x);
	}
	cnt++;
	a[cnt]=x;
	r[x]=cnt;
}
void change(int x,long long y)
{
	for(;x<=2*n;x+=x&-x)
	{
		c[x]+=y;
	}
}
long long ask(int x)
{
	long long s=0;
	for(;x;x-=x&-x)
	{
		s+=c[x];
	}
	return s;
}
void dfs2(int x,int fa)
{
	ans-=(ask(r[x])-ask(l[x]-1))/2;
	for(int i=h2[x];i;i=ne2[i])
	{
		int y=v2[i];
		if(y==fa) continue;
		dfs2(y,x);
	}
	ans+=(ask(r[x])-ask(l[x]-1))/2;
	change(l[x],1);
	change(r[x],1);
}
int main()
{
	freopen("monkeyclim.in","r",stdin);
	freopen("monkeyclim.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add1(x,y);
		add1(y,x);
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add2(x,y);
		add2(y,x);
	}
	dfs1(1,0);
	dfs2(1,0);
	printf("%lld",ans);
	return 0;
}