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
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') flag = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
res = (res << 3) + (res << 1) + c - '0', c = getchar();
if(flag) res = -res;
}
const int N = 100010, M = N << 1;
int n;
int idx;
int h[N], e[M], ne[M];
LL ans[N], sum;
int color[N], cnt[N], sz[N], son[N];
int mx;
void add(int x, int y)
{
idx ++;
e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
void dfs(int x, int father)
{
sz[x] = 1;
for(int i = h[x]; ~i;i = ne[i])
{
int j = e[i];
if(j == father) continue;
dfs(j, x);
sz[x] += sz[j];
if(sz[j] > sz[son[x]]) son[x] = j;
}
}
void update(int x, int father, int y, int pson)
{
int c = color[x];
cnt[c] += y;
if(cnt[c] > mx) mx = cnt[c], sum = c;
else if(cnt[c] == mx) sum += c;
for(int i = h[x]; ~i;i = ne[i])
{
int j = e[i];
if(j == father || j == pson) continue;
update(j, x, y, pson);
}
}
void dfs2(int x, int father, int op)
{
for(int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
if(j == son[x] || j == father) continue;
dfs2(j, x, 0);
}
if(son[x]) dfs2(son[x], x, 1);
update(x, father, 1, son[x]);
ans[x] = sum;
if(!op) update(x, father, -1, 0), sum = mx = 0;
}
int main()
{
memset(h, -1, sizeof(h));
read(n);
for(int i = 1;i <= n;i ++) read(color[i]);
for(int i = 1;i < n;i ++)
{
int a, b;
read(a), read(b);
add(a, b), add(b, a);
}
dfs(1, -1);
dfs2(1, -1, 1);
for(int i = 1;i <= n;i ++) cout << ans[i] << " ";
return 0;
}
|