比赛 |
20241128 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
猴猴的比赛 |
最终得分 |
100 |
用户昵称 |
wdsjl |
运行时间 |
0.552 s |
代码语言 |
C++ |
内存使用 |
4.74 MiB |
提交时间 |
2024-11-28 11:01:39 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x
const int N=100010;
int sum[N];
void add(int x,int v){
while(x<N){
sum[x]+=v;
x+=lowbit(x);
}
}
int ask(int x){
int res=0;
while(x){
res+=sum[x];
x-=lowbit(x);
}
return res;
}
struct node{
int to,ne;
}e[N*2];
int n,h[N],tot;
void ade(int u,int y){
e[tot]={y,h[u]};
h[u]=tot++;
}
int ans[N],siz[N],od[N],cnt;
void dfs1(int u,int fa){
od[u]=++cnt;
siz[u]=1;
for(int i=h[u];~i;i=e[i].ne){
int v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
siz[u]+=siz[v];
}
}
void dfs2(int u,int fa){
int cmp=0;
for(int i=h[u];~i;i=e[i].ne){
int y=e[i].to;
if(y==fa) continue;
cmp=ask(od[y]+siz[y]-1)-ask(od[y]-1);
dfs2(y,u);
ans[y]-=cmp;
add(od[y],1);
}
ans[u]=ask(od[u]+siz[u]-1)-ask(od[u]-1);
}
int main(){
freopen("monkeyclim.in","r",stdin);
freopen("monkeyclim.out","w",stdout);
memset(h,-1,sizeof(h));
int x,y;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
ade(x,y);
}
dfs1(1,0);
tot=0;
memset(h,-1,sizeof(h));
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
ade(x,y);
}
dfs2(1,0);
for(int i=1;i<=n;i++)ans[0]+=ans[i];
printf("%d",ans[0]);
return 0;
}