「CF600E」Lomsat gelral - 树上启发式合并

Link: Problem - 600E - Codeforces

简要题意

对于一颗大小为 n , 根为 1 的有根树上的每个非叶子结点, 输出其子树中最多颜色的节点的编号的和

题面

You are given a rooted tree with root in vertex 1 . Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c . So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v .

Input

The first line contains integer n (1 \leq n \leq 10^5) — the number of vertices in the tree.

The second line contains n integers c_i (1 \leq c_i \leq n) , c_i — the colour of the i -th vertex.

Each of the next n - 1 lines contains two integers x_j, y_j (1 \leq x_j, y_j \leq n) — the edge of the tree. The first vertex is the root of the tree.

Output

Print n integers — the sums of dominating colours for each vertex.

Examples

input

1
2
3
4
5
4
1 2 3 4
1 2
2 3
2 4

output

1
10 9 3 4

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13

output

1
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

题解

DSU on tree (树上启发式合并)板子题, 当然也可以使用线段树合并的方法

首先进行树链剖分, 先统计轻节点的答案, 再统计重节点的答案, 合并即可, 这里要注意消除影响

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
#include <algorithm>
#include <cstdio>

typedef long long ll;

const int N = 100000 + 100;

struct Edge {
int to;
int nx;

Edge () {}
Edge (int t, int n) : to(t), nx(n) {}
};

int tot;
int hd[N];
Edge e[N << 1];

inline void add (int u, int v) {
e[++tot] = Edge(v, hd[u]), hd[u] = tot;
}

int now;

int h[N]; // heavy child node
int b[N]; // bucket
int siz[N]; // node size
int vis[N];
int cnt[N];

ll val[N]; // color
ll ans[N]; // result
ll sum[N];

void dfs (int u, int fa = 0) { // Split chain on tree
siz[u] = 1;
for (int i = hd[u]; i; i = e[i].nx) {
int v = e[i].to;
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
if (siz[v] > siz[h[u]]) h[u] = v;
}
}

void upd (int u, int fa = 0, int fl = 1) {
int &t = cnt[val[u]];
b[t]--, sum[t] -= val[u]; // delete in the bucket
t += fl;
b[t]++, sum[t] += val[u]; // add
if (fl > 0) now = std::max (now, t);
else if (!b[now]) now--;
for (int i = hd[u]; i; i = e[i].nx) {
int v = e[i].to;
if (v == fa || vis[v]) continue;
upd (v, u, fl);
}
}

void solve (int u, int fa = 0, int fl = 1) {
for (int i = hd[u]; i; i = e[i].nx) {
int v = e[i].to;
if (v == fa || v == h[u]) continue; // Calculate light child nodes
solve(v, u, 0);
}
if (h[u]) solve(h[u], u), vis[h[u]] = 1; // Calculate heavy child nodes
upd (u, fa);
ans[u] = sum[now], vis[h[u]] = 0; // Combined information
if (!fl) upd(u, fa, -1); // Eliminate the impact
}

int main () {
int n, u, v;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", val + i);
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
add(u, v); add(v, u);
}
dfs(1);
solve(1);
for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!