比赛 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;
}