题目描述

我们有一个包含 $N$ 个顶点的树，顶点编号从 $1$ 到 $N$。树中的第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。此外，每个顶点都被涂成了一种颜色，第 $i$ 个顶点的颜色是 $c_i$。这里，每个顶点的颜色用一个介于 $1$ 和 $N$（包括 $1$ 和 $N$）之间的整数表示。相同的整数对应于相同的颜色；不同的整数对应于不同的颜色。

对于每个 $k=1, 2, ..., N$，解决以下问题：

• 找到访问至少一次被涂成颜色 $k$ 的顶点的简单路径数量。

注意： 从顶点 $u$ 到 $v$ 的简单路径和从 $v$ 到 $u$ 的简单路径是不加区分的。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq c_i \leq N$
• $1 \leq a_i,b_i \leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

---

输入

输入以以下格式从标准输入给出：

$N$

$c_1$ $c_2$ $...$ $c_N$

$a_1$ $b_1$

$:$

$a_{N-1}$ $b_{N-1}$

输出

按顺序打印 $k = 1, 2, ..., N$ 的答案，每个答案单独一行。

---

示例输入 1

3
1 2 1
1 2
2 3

示例输出 1

5
4
0

假设 $P_{i,j}$ 表示连接顶点 $i$ 和 $j$ 的简单路径。

有 $5$ 条简单路径访问至少一次被涂成颜色 $1$ 的顶点：
$P_{1,1}、P_{1,2}、P_{1,3}、P_{2,3}、P_{3,3}$

有 $4$ 条简单路径访问至少一次被涂成颜色 $2$ 的顶点：
$P_{1,2}、P_{1,3}、P_{2,2}、P_{2,3}$

没有简单路径访问至少一次被涂成颜色 $3$ 的顶点。

---

示例输入 2

1
1

示例输出 2

1

---

示例输入 3

2
1 2
1 2

示例输出 3

2
2

---

示例输入 4

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

示例输出 4

5
8
10
5
5

---

示例输入 5

8
2 7 2 5 4 1 7 5
3 1
1 2
2 7
4 5
5 6
6 8
7 8

示例输出 5

18
15
0
14
23
0
23
0