codeforces - 600E Lomsat gelral

题目链接：Lomsat gelral

题目大意：就是求任意一个子树的出现最多的颜色的值，如果出现次数一样则累加。

然后就是一道树上启发式合并的裸题啦！

我们每次用重链维护信息，往上传递，其他信息暴力更新即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,c[N],cnt[N],mx,sum,res[N],sz[N],son[N],skip;
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		dfs(to[i],x);	sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]])	son[x]=to[i];
	}
}
void updata(int x,int fa,int k){
	cnt[c[x]]+=k;
	if(x>0&&cnt[c[x]]>mx)	mx=cnt[c[x]],sum=c[x];
	else if(x>0&&cnt[c[x]]==mx)	sum+=c[x];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa&&to[i]!=skip)	updata(to[i],x,k);
	}
}
void solve(int x,int fa,int k){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa&&to[i]!=son[x])	solve(to[i],x,0);
	}
	if(son[x])	solve(son[x],x,1),skip=son[x];
	updata(x,fa,1);	res[x]=sum; skip=0;
	if(!k)	updata(x,fa,-1),mx=sum=0;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>c[i];
	for(int i=1;i<n;i++){
		int a,b;	cin>>a>>b;	add(a,b);	add(b,a);
	}
	dfs(1,0);	solve(1,0,0);
	for(int i=1;i<=n;i++)	cout<<res[i]<<" ";puts("");
	return 0;
}