You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

有一棵 $n$ 个点的树，第 $i$ 条边连接 $a_i$ 和 $b_i$ ，第 $i$ 个点颜色为 $c_i$。

对于每个 $k=1,2,..., n$ ，计算经过颜色 $k$ 的简单路径的数目。

路径 $i$ 到 $j$ 与 路径 $j$ 到 $i$ 视为相同的路径。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $c_1, c_2, \dots , c_n$。

接下来 $n-1$ 行，每行两个整数 $a_i, b_i$，表示一条边。

输出格式

$n$ 行，每行一个整数。

样例输入1

3
1 2 1
1 2
2 3

样例输出1

5
4
0

样例解释1

用 $p_{i,j}$ 表示端点为 $i$ 和 $j$ 的简单路径

经过颜色1的简单路径有 5条：$p_{1,1}, p_{1,2}, p_{1,3}, p_{2,3}, p_{3,3}$

经过颜色2的简单路径有 4条：$p_{1,2}, p_{1,3}, p_{2,2}, p_{2,3}$。

没有经过颜色3的简单路径。

样例输入2

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

样例输出2

18
15
0
14
23
0
23
0

###　数据范围

$1 \le n \le 2*10^5； 1\le a_i, b_i, c_i \le n$