比赛 |
20241128 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
猴猴的比赛 |
最终得分 |
100 |
用户昵称 |
小金 |
运行时间 |
0.592 s |
代码语言 |
C++ |
内存使用 |
5.95 MiB |
提交时间 |
2024-11-28 11:54:07 |
显示代码纯文本
#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;
}