n个点的有根树，以1为根，每个点有一种颜色。我们称一种颜色占领了一个子树当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和。

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 30010010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,hson[maxn],size[maxn],ans[maxn],c[maxn],cnt[maxn],sum,mx,S;13 vector<llg>a[maxn];14 15 inline llg getint()16 {17        llg w=0,q=0; char c=getchar();18        while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 19        while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;20 }21 22 void init()23 {24     llg x,y;25     cin>>n;26     for (llg i=1;i<=n;i++) c[i]=getint();27     for (llg i=1;i<n;i++)28     {29         x=getint(),y=getint();30         a[x].push_back(y),a[y].push_back(x);31     }32 }33 34 void find_hson(llg x,llg fa)35 {36     size[x]=1;37     llg w=a[x].size(),v;38     for (llg i=0;i<w;i++)39     {40         v=a[x][i];41         if (v==fa) continue;42         find_hson(v,x);43         size[x]+=size[v];44         if (size[v]>size[hson[x]]) hson[x]=v;45     }46 }47 48 void calc(llg x,llg fa,llg val)49 {50     cnt[c[x]]+=val;51     if (cnt[c[x]]>mx) sum=c[x],mx=cnt[c[x]];52     else53     {54         if (cnt[c[x]]==mx) sum+=c[x];55     }56     llg w=a[x].size(),v;57     for (llg i=0;i<w;i++)58     {59         v=a[x][i];60         if (v==fa || v==S) continue;61         calc(v,x,val);62     }63 }64 65 void dfs(llg x,llg fa,llg t)66 {67     llg w=a[x].size(),v;68     for (llg i=0;i<w;i++)69     {70         v=a[x][i];71         if (v==fa || v==hson[x]) continue;72         dfs(v,x,-1);73     }74     if (hson[x]) dfs(hson[x],x,1),S=hson[x];75     calc(x,fa,1); S=0;76     ans[x]=sum;77     if (t==-1) calc(x,fa,-1),mx=sum=0;78 }79 80 int main()81 {82     yyj("tree");83     init();84     find_hson(1,0);85     dfs(1,0,1);86     for (llg i=1;i<=n;i++) printf("%lld ",ans[i]);87     return 0;88 }