F - 过路径 i

分数：$600$ 分

问题描述

给定一个包含 $N$ 个顶点的树，编号从 $1$ 到 $N$。树中的第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。 另外，每个顶点都被涂上了一种颜色，第 $i$ 个顶点的颜色是 $c_i$。这里，每个顶点的颜色用一个 $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$ 的答案，每个占一行。

---

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