← 返回题目列表

Codeforces · 600/E

E. Lomsat 凝胶

中文机器翻译题面 查看原题

给你一棵有根树,根位于顶点 1。每个顶点都涂上某种颜色。

如果没有其他颜色在顶点 v 的子树中出现的次数多于颜色 c,我们称颜色 c 在顶点 v 的子树中占主导地位。因此,有可能两种或多种颜色在某个顶点的子树中占主导地位。

顶点 v 的子树是顶点 v 以及到根的每条路径中包含顶点 v 的所有其他顶点。

对于每个顶点 v 求顶点 v 的子树中所有主颜色的总和。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 树中的顶点数。

第二行包含n个整数ci (1 ≤ ci ≤ n),ci — 第i个顶点的颜色。

接下来的 n - 1 行中的每一行都包含两个整数 xj, yj (1 ≤ xj, yj ≤ n) — 树的边缘。第一个顶点是树的根。

输出

打印 n 个整数 — 每个顶点的主颜色之和。

示例

输入 #1

4
1 2 3 4
1 2
2 3
2 4

输出 #1

10 9 3 4

输入 #2

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

输出 #2

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