1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>a
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
struct E{
int to,next;
}Edge[maxn<<1];
int tot,Head[maxn];
inline void AddEdge(int u,int v){
Edge[tot].to=v;
Edge[tot].next=Head[u];
Head[u]=tot++;
}
int siz[maxn],son[maxn];
void dfs (int u,int f){//与重链剖分相同的写法找重儿子
siz[u]=1;
for (int i=Head[u];~i;i=Edge[i].next){
int v=Edge[i].to;
if (v==f) continue;
dfs (v,u);
siz[u]+=siz[v];
if (siz[v]>siz[son[u]]){
son[u]=v;
}
}
}
int col[maxn],cnt[maxn];//col存放某结点的颜色,cnt存放某颜色在“当前”子树的数量
long long ans[maxn],sum;//ans是答案数组,sum用于累加计算出“当前”子树的答案
int flag,maxc;//flag用于标记重儿子,maxc用于更新最大值
//TODO 统计某结点及其所有轻儿子的贡献
void count(int u,int f,int val){
cnt[col[u]]+=val;//val为正为负可以控制是增加贡献还是删除贡献
if (cnt[col[u]]>maxc){//找最大值
maxc=cnt[col[u]];
sum=col[u];
}else if (cnt[col[u]]==maxc){
sum+=col[u];
}
for (int i=Head[u];~i;i=Edge[i].next){
int v=Edge[i].to;
if (v==f||v==flag){
continue;
}
count (v,u,val);
}
}
//DSU on tree的板子
void dfs (int u,int f,bool keep){
// 第一步搞轻儿子及其子树算其答案删除贡献
for (int i=Head[u];~i;i=Edge[i].next){
int v=Edge[i].to;
if (v==f||v==son[u]){
continue;
}
dfs (v,u,false);
}
//第二步,搞重儿子及其子树算其答案不删贡献
if(son[u]){
dfs (son[u],u,true);
flag=son[u];
}
//第三步,暴力统计u及其所有轻儿子的贡献合并到刚算出的重儿子信息里(sum)
count(u,f,1);
flag=0;
ans[u]=sum;
//把需要删除贡献的删一删
if (!keep){//如果u是轻儿子
count(u,f,-1);//刚才 +1现在-1清除贡献
sum=maxc=0;//sum,maxc置零
}
}
int main ()
{
memset(Head,-1,sizeof (Head));
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>col[i];
}
for (int i=1,u,v;i<n;i++){
cin>>u>>v;
AddEdge(u,v);
AddEdge(v,u);
}
dfs (1,0);
dfs (1,0,0);
for (int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
return 0;
}