410132: GYM103960 L Listing Tedious Paths

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Listing Tedious Pathstime limit per test1.0 smemory limit per test1024 megabytesinputstandard inputoutputstandard output

A tree is a graph that is connected (there exists a path between any two of its vertices), undirected (the edges of the graph have no direction), and acyclic (there are no cycles).

A colorful tree is a tree in which each of its vertices has a specific color.

A tedious path is a path in the tree such that both the initial and final vertices have the same color, and there is no vertex or edge that appear more than once in the path. Note that the color of the intermediate vertices, if there are any, are irrelevant.

Given a colorful tree, with $$$N$$$ vertices, your task is calculate, for each of the edges, the number of tedious paths that go through that edge.

Input

The first line contains the number of vertices $$$N$$$ ($$$2 \le N \le 10^5$$$). The second line contains $$$N$$$ integers $$$C_1, \dots, C_N$$$, where $$$C_i$$$ ($$$1 \le C_i \le N$$$) represents the color of the vertex $$$i$$$. The next $$$N - 1$$$ lines contains two integers each, $$$u$$$ and $$$v$$$, representing an edge ($$$1 \le u, v \le N$$$ and $$$u \ne v$$$). It's guaranteed that the given graph is a tree.

Output

Print $$$N-1$$$ integers, representing the number of tedious paths that go through each edge, following the same order of the edges as they are given in the input.

ExamplesInput
6
1 1 1 2 2 1
1 2
2 3
4 6
2 4
1 5
Output
4 3 3 4 1
Input
12
1 2 3 1 2 2 1 3 2 3 1 2
1 2
2 3
2 4
4 5
4 6
1 7
7 8
7 9
9 10
6 11
6 12
Output
10 2 10 4 9 9 2 6 2 3 4

加入题单

上一题 下一题 算法标签: