显然加入和删除点可以
O(1)
维护。先做一次树剖，然后从根开始
dfs
一遍。
dfs
到一个点时加入答案。对于每个点如果是轻儿子退出时删除，否则不删除。统计答案时暴力
dfs
一遍所有轻儿子。 因为一个点到根路径上只有
O(logn)
条轻边，所以最多只会被统计
O(logn)
次。时间复杂度为
O(nlogn)
。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define ll long long
vector<int>g[N];
ll Sum[N],Ans[N];
int i,j,k,n,m,M,sz[N],s[N],a[N],Res,c[N],x,y;
inline int Max(
int x,
int y){
return x<y?y:x;
}
inline void Dfs1(
int x,
int y){
sz[x]=
1;
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=y){
Dfs1(g[x][i],x);
sz[x]+=sz[g[x][i]];
if(sz[g[x][i]]>sz[s[x]])s[x]=g[x][i];
}
}
inline void Add(
int x){
Sum[++c[x]]+=x;
Sum[c[x]-
1]-=x;
Res=Max(Res,c[x]);
}
inline void Del(
int x){
Sum[c[x]]-=x;
if(!Sum[c[x]]&&Res==c[x])Res--;
Sum[--c[x]]+=x;
}
inline void Dfs2(
int x,
int y,
bool d){
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=y)Dfs2(g[x][i],x,d);
if(d)Add(a[x]);
else Del(a[x]);
}
inline void Dfs(
int x,
int y,
bool d){
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=y&&g[x][i]!=s[x])Dfs(g[x][i],x,
0);
if(s[x])Dfs(s[x],x,
1);Add(a[x]);
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=y&&g[x][i]!=s[x])Dfs2(g[x][i],x,
1);
Ans[x]=Sum[Res];
if(!d){
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=y)Dfs2(g[x][i],x,
0);
Del(a[x]);
}
}
int main(){
scanf(
"%d",&n);
for(i=
1;i<=n;i++)
scanf(
"%d",&a[i]);
for(i=
1;i<n;i++)
scanf(
"%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
Dfs1(
1,
0);
Dfs(
1,
0,
1);
for(i=
1;i<=n;i++)
printf(
"%I64d ",Ans[i]);
return 0;
}
