题目描述

We have a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge in this tree connects Vertex $a_i$ and $b_i$. Additionally, each vertex is painted in a color, and the color of Vertex $i$ is $c_i$. Here, the color of each vertex is represented by an integer between $1$ and $N$ (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.

For each $k=1, 2, ..., N$, solve the following problem:

• Find the number of simple paths that visit a vertex painted in the color $k$ one or more times.

Note: The simple paths from Vertex $u$ to $v$ and from $v$ to $u$ are not distinguished.

我们有一棵树，树上有 $N$ 个顶点，编号从 $1$ 到 $N$ 。树中的 $i$ 条边连接顶点 $a_i$ 和 $b_i$ 。此外，每个顶点都涂有一种颜色，顶点 $i$ 的颜色是 $c_i$ 。在这里，每个顶点的颜色由一个介于 $1$ 和 $N$ 之间的整数表示。(包括在内）。相同的整数对应相同的颜色，不同的整数对应不同的颜色。

请为每个 $k=1, 2, ..., N$ 解决以下问题：

• 求访问颜色为 $k$ 的顶点一次或多次的简单路径的数目。

注： 从顶点 $u$ 到 $v$ 以及从 $v$ 到 $u$ 的简单路径不作区分。

输入格式

输入内容按以下格式标准输入：

$N$
$c_1$ $c_2$ $...$ $c_N$
$a_1$ $b_1$
$:$
$a_{N-1}$ $b_{N-1}$

输出格式

依次打印 $k = 1, 2, ..., N$ 的答案，每个答案各占一行。

样例 #1

样例输入 #1

3
1 2 1
1 2
2 3

样例输出 #1

5
4
0

样例 #2

样例输入 #2

1
1

样例输出 #2

1

样例 #3

样例输入 #3

2
1 2
1 2

样例输出 #3

2
2

样例 #4

样例输入 #4

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

样例输出 #4

5
8
10
5
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

说明

数据规模与约定

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq c_i \leq N$
• $1 \leq a_i,b_i \leq N$
• 给定图形是一棵树。
• 输入值均为整数。

样例 $1$ 解释

让 $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$ 的顶点一次或多次。