( ext{Solution:})
树上启发式合并，是对普通暴力的一种优化。
考虑本题，最暴力的做法显然是暴力统计每一次的子树，为了避免其他子树影响，每次统计完子树都需要清空其信息。
但是，如果我们先对非(x)的节点进行统计，最后统计(x)然后合并其他节点的信息，那么，(x)的统计信息就没有必要被删掉。
那么显然地，(x)的子树越大越好。
于是，自然想到轻重链剖分，并将(x)设置为其重儿子。于是，算法模型如下：
-
对所有非重儿子进行统计并清空其所记录的统计信息。
-
对重儿子进行统计并保留其信息。
-
暴力将其他儿子的信息合并到重儿子上，得到当前子树的信息。
根据树链剖分的性质，一个点到根的路径上的轻边条数不超过(log n)条，而一个节点只有其祖先遇到轻边的时候才会被统计一次。
所以复杂度为(O(nlog n).)
关于这题 直接安装上述算法流程进行暴力统计即可。
关于一点对树剖性质的证明：每次经过一条轻边，其子树大小最少会变成原来的一半，所以轻边条数是(O(log n))的。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
typedef long long ll;
int son[MAXN],head[MAXN],n,tot,siz[MAXN];
int vis[MAXN],cnt[MAXN],col[MAXN],Mx,Son;
vector<int>v[MAXN];
ll sum,ans[MAXN];
void dfs(int x,int fa){
siz[x]=1;
for(int i=0;i<v[x].size();++i){
int j=v[x][i];
if(j==fa)continue;
dfs(j,x);siz[x]+=siz[j];
if(siz[j]>siz[son[x]])son[x]=j;
}
}
void add(int x,int fa,int val){
cnt[col[x]]+=val;
if(cnt[col[x]]>Mx)Mx=cnt[col[x]],sum=col[x];
else if(cnt[col[x]]==Mx)sum+=col[x]*1ll;
for(int i=0;i<v[x].size();++i){
int j=v[x][i];
if(j==fa||j==Son)continue;
add(j,x,val);
}
}
void dfs2(int x,int fa,int opt){
for(int i=0;i<v[x].size();++i){
int j=v[x][i];
if(j==fa)continue;
if(j!=son[x])dfs2(j,x,0);
}
if(son[x])dfs2(son[x],x,1),Son=son[x];
add(x,fa,1);Son=0;
ans[x]=sum;
if(!opt)add(x,fa,-1),sum=Mx=0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",col+i);
for(int i=1;i<n;++i){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);v[y].push_back(x);
}
dfs(1,0);dfs2(1,0,0);
for(int i=1;i<=n;++i)printf("%I64d ",ans[i]);
puts("");
return 0;
}