途经颜色 k 的路径

题目描述

有一棵具有 $1$ 到 $N$ 编号的 $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$ 各问题的答案。

样例

3
1 2 1
1 2
2 3

5
4
0

用 $P_{i,j}$ 表示连接顶点 $i$ 与顶点 $j$ 的简单路径。

至少经过一次涂有颜色 $1$ 的顶点的简单路径有

$P_{1,1}\,,\,$
$P_{1,2}\,,\,$
$P_{1,3}\,,\,$
$P_{2,3}\,,\,$
$P_{3,3}$

这 $5$ 条。

至少经过一次涂有颜色 $2$ 的顶点的简单路径有

$P_{1,2}\,,\,$
$P_{1,3}\,,\,$
$P_{2,2}\,,\,$
$P_{2,3}$

这 $4$ 条。

不存在经过涂有颜色 $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$
• 给出的图是一棵树。
• 输入均为整数。