受hpdf的影响我来学DSU on tree了
板子题都A不了。。。WA#25,求助dalao/kel
#include<cstdio>
const int M=1e5+5;
int n,son[M],cnt[M],color[M];
int Son,Max,sum,ans[M];
struct Edge{
int to;
Edge*nx;
}e[M<<1],*h[M],*tot=e;
inline void Add(int u,int v){
*tot=(Edge){v,h[u]};h[u]=tot++;
*tot=(Edge){u,h[v]};h[v]=tot++;
}
void DFS(int u,int f){
int max=0;
cnt[u]=1;
for(Edge*E=h[u];E;E=E->nx){
int v=E->to;
if(v==f)continue;
DFS(v,u);
cnt[u]+=cnt[v];
if(cnt[v]>max)max=cnt[v],son[u]=v;
cnt[v]=0;
}
}
void change(int u,int f,int val){
cnt[color[u]]+=val;
if(cnt[color[u]]>Max)Max=cnt[sum=color[u]];
else if(cnt[color[u]]==Max)Max+=color[u];
for(Edge*E=h[u];E;E=E->nx){
int v=E->to;
if(v==f||v==Son)continue;
change(v,u,val);
}
}
void Solve(int u,int f,bool keep){
for(Edge*E=h[u];E;E=E->nx){
int v=E->to;
if(v==f||v==son[u])continue;
Solve(v,u,false);
}
if(son[u])Solve(son[u],u,true),Son=son[u];
change(u,f,1);ans[u]=sum;Son=0;
if(!keep)change(u,f,-1),sum=Max=0;
}
signed main(){
int i,x,y;
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",color+i);
for(i=1;i<n;++i){
scanf("%d%d",&x,&y);
Add(x,y);
}
DFS(1,0);cnt[1]=0;
Solve(1,0,false);
for(i=1;i<=n;++i)printf("%d ",ans[i]);
}