比赛 |
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
*/