树上启发式合并（常常也叫DSU On Tree，但其实和DSU并没有特别大关系），是一种解决某些树上离线问题的算法，尤其常被用于解决“对每个节点，询问关于其子树的某些信息”这样的问题。
- 假设我们要对树上的每个节点p求ans[p] ，且这个ans[p] 可以通过合并p的子节点的某些信息得知，一般来说我们可以用树形DP解决。但如果“子节点的某些信息”的规模较大，简单的树形DP在时间和空间上都可能爆炸。所以我们不能存储每个节点的信息，而是要实现某种资源复用。
- 有一棵 \(n\) 个结点的以 \(1\) 号结点为根的有根树。
- 每个结点都有一个颜色，颜色是以编号表示的， \(i\) 号结点的颜色编号为 \(c_i\)。
- 如果一种颜色在以 \(x\) 为根的子树内出现次数最多，称其在以 \(x\) 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
- 你的任务是对于每一个 \(i\in[1,n]\)，求出以 \(i\) 为根的子树中，占主导地位的颜色的编号和。
- \(n\le 10^5,c_i\le n\)
时间复杂度O（nlogn)
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;
}