题目描述

给定一个包含 $N$ 个顶点的树，编号从$1$到 $N$。

树中的第$i$条边连接顶点$a_i$和$b_i$。

另外，每个顶点都被涂上了一种颜色，第$i$个顶点的颜色是 $c_i$。

这里，每个顶点的颜色用一个$1$到 $N$ 之间(包括边界)的整数表示。

同样的整数代表相同的颜色，不同的整数代表不同的颜色。

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

找到访问至少一个被染上颜色的顶点的简单路径的数量,注意:从顶点 $u$ 到$υ$和从 $υ$到 $u$的简单路径是没有区别的。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，表示 $c_i$。

接下来第 $3$ 到第 $n+1$ 行，每行两个整数 $u_i,v_i$，描述一条树边。

输出格式

输出 $n$ 行，一行一个整数，分别表示对于颜色 $1,2,...,n$ 的答案。

3
1 2 1
1 2
2 3

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$ 的顶点的简单路径,

1
1

1

2
1 2
1 2

2
2

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

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

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$
• 给定的图是一棵树。
• 输入中的所有值都是整数。