#include<bits/stdc++.h>
#define LL long long 
using namespace std;
int read(){
  char c=getchar(); int x=0,f=1;
  while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
  while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
  return x*f;
}

const int N=1e5+10;
// col[x]:节点的颜色编号, son[x]:重儿子, 
// cnt[i]:颜色编号i的数量
int n,col[N],siz[N],son[N],cnt[N],mx;
LL sum,ans[N];
vector<int> e[N];

void dfs1(int x,int fa){ //重链剖分
  siz[x]=1;
  for(int y : e[x]){
    if(y==fa) continue;
    dfs1(y,x);
    siz[x]+=siz[y];
    if(siz[y]>siz[son[x]]) son[x]=y;
  }
}
void add(int x,int fa,int son){
  cnt[col[x]]++;
  if(cnt[col[x]]>mx) mx=cnt[col[x]],sum=col[x];
  else if(cnt[col[x]]==mx) sum+=col[x];
  
  for(int y : e[x]) //重子树除外
    if(y!=fa && y!=son) add(y,x,son);
}
void sub(int x,int fa){
  cnt[col[x]]--;
  for(int y : e[x])
    if(y!=fa) sub(y,x);
}
void dfs2(int x, int fa, int opt){
  for(int y : e[x]) //先搜轻儿子
    if(y!=fa && y!=son[x]) dfs2(y,x,0);
  if(son[x]) dfs2(son[x],x,1); //后搜重儿子
  
  add(x,fa,son[x]); //累加x和轻子树贡献
  ans[x]=sum;       //存储答案
  if(!opt)sub(x,fa),sum=mx=0; //减掉轻子树贡献
}
int main(){
  n=read();
  for(int i=1; i<=n; i++) col[i]=read();
  for(int i=1; i<=n-1; i++){
    int x=read(),y=read();
    e[x].push_back(y); e[y].push_back(x);
  }
  dfs1(1,0);
  dfs2(1,0,0);
  for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
  return 0;
}

D32 树上启发式合并 CF600E Lomsat gelral
暴力80分，超时（无启发式，不考虑保留重儿子影响）的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename T>void qr(T& x) 
{
    x=0;int f=1;char c=getchar();
    for( ; !isdigit(c); c=getchar())if(c=='-')f=-1;
    for( ; isdigit(c); c=getchar())x=x*10+c-48;
    x=x*f;
}
const int N=1e5+10;
int n,tsp,dfn[N],rnk[N],siz[N],col[N],cnt[N],mx;
LL sum,ans[N];
vector<int>G[N];
void dfs1(int x,int fa)
{
    dfn[x]=++tsp;
    rnk[tsp]=x;
    siz[x]=1;
    for(int y : G[x]) if(y!=fa)
    {
        dfs1(y,x);
        siz[x]+=siz[y];
    }
}
void add(int x) 
{
    cnt[col[x]]++;
    if(cnt[col[x]]>mx) mx=cnt[col[x]],sum=col[x];
    else if(cnt[col[x]]==mx) sum+=col[x];
}
 
void dfs2(int x, int fa) 
{
    for(int y : G[x])if(y!=fa)
        dfs2(y,x);
         
    sum=mx=0;
    for(int i=0;i<siz[x];i++) add(rnk[dfn[x]+i]);
             
    ans[x]=sum;  //存储答案
     
    sum=mx=0;
    for(int i=0;i<siz[x];i++) cnt[col[rnk[dfn[x]+i]]]--;
 
}
int main() 
{
    qr(n);for(int i=1; i<=n; i++) qr(col[i]);
    for(int i=1,x,y; i<=n-1; i++) 
    {
        qr(x);qr(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    tsp=0;dfs1(1,0);
    memset(ans,0,sizeof(ans));
    dfs2(1,0);
    for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
    return 0;
}

树上启发式代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename T>void qr(T& x) 
{
	x=0;int f=1;char c=getchar();
	for( ; !isdigit(c); c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c); c=getchar())x=x*10+c-48;
	x=x*f;
}
const int N=1e5+10;
int n,tsp,dfn[N],siz[N],son[N],rnk[N],col[N],cnt[N],mx;
LL sum,ans[N];
vector<int>G[N];
void dfs1(int x,int fa)
{
	dfn[x]=++tsp;
	rnk[tsp]=x;
	siz[x]=1;
	for(int y : G[x]) if(y!=fa)
	{
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}
void add(int x) 
{
	cnt[col[x]]++;
	if(mx<cnt[col[x]]) mx=cnt[col[x]],sum=col[x];
	else if(mx==cnt[col[x]])          sum+=col[x];
}
void dfs2(int x, int fa, bool keep) 
{
	for(int y : G[x])if(y!=fa && y!=son[x]) //先搜轻儿子
		dfs2(y,x,0);
	if(son[x]) dfs2(son[x],x,1); //后搜重儿子
	
	add(x);//累加x和轻子树贡献
	for(int y : G[x])if(y!=fa && y!=son[x])
		for(int i=0;i<siz[y];i++) 
			add(rnk[dfn[y]+i]); 
			
	ans[x]=sum;  //存储答案
	if(keep==0)//若x是上层的轻子树，则减去x所在子树的贡献
	{
		for(int i=0;i<siz[x];i++) cnt[col[rnk[dfn[x]+i]]]--;
		sum=mx=0; 
	}
}
int main() 
{
	qr(n);for(int i=1; i<=n; i++) qr(col[i]);
	for(int i=1,x,y; i<=n-1; i++) 
	{
		qr(x);qr(y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	memset(son,0,sizeof(son));memset(siz,0,sizeof(siz));
	tsp=0;dfs1(1,0);
	memset(ans,0,sizeof(ans));
	dfs2(1,0,1);
	for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
	return 0;
}