ABC163——Task F：path pass i - Problem - MYOJ

Problem5324--ABC163——Task F：path pass i

5324: ABC163——Task F：path pass i

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 256 MiB

Submit Solved: 1 Submit Num: 1 Statistics ShowOff!

Description

We have a tree with $N$ vertices numbered $1$ to $N$ . The $i$ -th edge in this tree connects Vertex $_{i}$ and $_{i}$ . Additionally, each vertex is painted in a color, and the color of Vertex $i$ is $_{i}$ . Here, the color of each vertex is represented by an integer between $1$ and $N$ (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.

For each $k = 1, 2, . . ., N$ , solve the following problem:

Find the number of simple paths that visit a vertex painted in the color $k$ one or more times.

Note: The simple paths from Vertex $u$ to $v$ and from $v$ to $u$ are not distinguished.

Input

Input is given from Standard Input in the following format:

N
c₁ c₂ ... c_N a₁ b₁ .
.
a_N b_N

Output

Print the answers for

k = 1, 2, . . ., N

k=1,2,...,N in order, each in its own line.

Sample 1 Input

Sample 1 Output

5
4
0

HINT

【样例 1 说明】

Let $_{i, j}$ denote the simple path connecting Vertex $i$ and $j$ .

There are $5$ simple paths that visit a vertex painted in the color $1$ one or more times:
$_{1, 1},$ $_{1, 2},$ $_{1, 3},$ $_{2, 3},$ $_{3, 3}$

There are $4$ simple paths that visit a vertex painted in the color $2$ one or more times:
$_{1, 2},$ $_{1, 3},$ $_{2, 2},$ $_{2, 3}$

There are no simple paths that visit a vertex painted in the color $3$ one or more times.
【样例 2 输入】

1
1

【样例 2 输出】

【样例 3 输入】

2
1 2
1 2

【样例 3 输出】

2
2

【样例 4 输入】

【样例 4 输出】

【样例 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 输出】

【数据范围】

$1 \leq N \leq 2 \times^{5}$
$1 \leq_{i} \leq N$
$1 \leq_{i},_{i} \leq N$
The given graph is a tree.
All values in input are integers.

【题目出处】
AtCoder Beginner Contest 163，Task F。https://atcoder.jp/contests/abc163/tasks/abc163_f

Source/Category

AtCoder_ABC 100.163.ABC163

Submit