CodeForces 600E Lomsat gelral

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n;
int g[MAXN],tot,col[MAXN],dfn,u,v;
int sz[MAXN],deep[MAXN],fa[MAXN],son[MAXN],L[MAXN],R[MAXN],index[MAXN],skp;
long long sum,ans[MAXN];
int cnt[MAXN],nowmax;
struct edges
{
    int to,next;
}e[2*MAXN];
void add_edge(int from,int to)
{
    e[++tot].to=to;
    e[tot].next=g[from];
    g[from]=tot;
    return;
}
void dfs(int x,int dep,int father)
{
    sz[x]=1;
    deep[x]=dep;
    fa[x]=father;
    son[x]=0;
    L[x]=++dfn;
    index[dfn]=x;
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs(e[i].to,dep+1,x);
            sz[x]+=sz[e[i].to];
            if(!son[x]||sz[son[x]]<sz[e[i].to])son[x]=e[i].to;
        }
    }
    R[x]=dfn;
    return;
}
void get_data(int x,int op)
{
    for(int i=L[x];i<=R[x];++i)
    {
        if(index[i]==skp)
        {
            i=R[index[i]];
            continue;
        }
        cnt[col[index[i]]]+=op;
        if(nowmax<cnt[col[index[i]]])
        {
            nowmax=cnt[col[index[i]]];
            sum=col[index[i]];
        }
        else if(nowmax==cnt[col[index[i]]])
        {
            sum+=col[index[i]];
        }
    }
}
void dsu(int x,int fa,bool del)
{
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to==fa||e[i].to==son[x])continue;
        dsu(e[i].to,x,true);
    }
    ///skip the heavy son
    if(son[x])
    {
        dsu(son[x],x,false);
        skp=son[x];
    }
    ///get data from light son and itself
    get_data(x,1);
    ans[x]=sum;
    ///if delete clear all
    if(del)
    {
        skp=0;
        get_data(x,-1);
        sum=0;
        nowmax=0;
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&col[i]);
    }
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,1,-1);
    dsu(1,-1,0);
    for(int i=1;i<=n;++i)
    {
        printf("%lld%c",ans[i],i==n?'\n':' ');
    }
    return 0;
}