本文共 1839 字，大约阅读时间需要 6 分钟。

题目描述

有一棵 \(n\) 个结点的以 \(1\) 号结点为根的有根树。

输入输出样例

输入 #1

4

1 2 3 4

1 2

2 3

2 4

输出 #1

10 9 3 4

输入 #2

15

1 2 3 1 2 3 3 1 1 3 2 2 1 2 3

1 2

1 3

1 4

1 14

1 15

2 5

2 6

2 7

3 8

3 9

3 10

4 11

4 12

4 13

输出 #2

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

分析

代码

#include
   
    #include
    
     inline int read(){	register int x=0,fh=1;	char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=2e5+5;int h[maxn],tot=1;struct asd{	int to,nxt;}b[maxn];void ad(int aa,int bb){	b[tot].to=bb;	b[tot].nxt=h[aa];	h[aa]=tot++;}int n,c[maxn],f[maxn],son[maxn],siz[maxn];void dfs(int now,int fa){	siz[now]=1;	f[now]=fa;	for(register int i=h[now];i!=-1;i=b[i].nxt){		register int u=b[i].to;		if(u==fa) continue;		dfs(u,now);		siz[now]+=siz[u];		if(son[now]==0 || siz[son[now]]
     
      mmax){		mmax=cnt[c[now]];		sum=c[now];	} else if(cnt[c[now]]==mmax){		sum+=c[now];	}	for(int i=h[now];i!=-1;i=b[i].nxt){		int u=b[i].to;		if(u==f[now] || u==orz) continue;		xg(u,val);	}}//删除/加入贡献void dfs2(int now,int op){	for(register int i=h[now];i!=-1;i=b[i].nxt){		register int u=b[i].to;		if(u==f[now] || u==son[now]) continue;		dfs2(u,0);	}	if(son[now]){		dfs2(son[now],1);		orz=son[now];	} 	xg(now,1);	orz=0;	ans[now]=sum;	if(op==0){		xg(now,-1);		sum=mmax=0;	}}//求出答案int main(){	memset(h,-1,sizeof(h));	n=read();	for(register int i=1;i<=n;i++){		c[i]=read();	}	int aa,bb;	for(register int i=1;i