分数: 600 点
问题陈述
我们有一棵树 N 顶点编号 1 to N。的 i此树中的第一条边连接顶点 a_i 和 b_i。 此外,每个顶点都涂有一种颜色,并且顶点的颜色 i is c_i。这里,每个顶点的颜色由一个介于 1 和 N (含)。相同的整数对应相同的颜色;不同的整数对应不同的颜色。
对于每个 k=1, 2, ..., N,解决以下问题:
- 查找访问用该颜色绘制的顶点的简单路径的数量 k 一次或多次。
注意: 来自 Vertex 的简单路径 u to v 和来自 v to 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 按顺序,各占一行。
示例输入 1
3 1 2 1 1 2 2 3
示例输出 1
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 一次或多次。
示例输入 2
1 1
示例输出 2
1
示例输入 3
2 1 2 1 2
示例输出 3
2 2
示例输入 4
5 1 2 3 4 5 1 2 2 3 3 4 3 5
示例输出 4
5 8 10 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