← 返回题目列表

AtCoder · abc163_f

F. 路径通过我

中文机器翻译题面 查看原题

分数: 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