410132: GYM103960 L Listing Tedious Paths
Description
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.
InputThe 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.
OutputPrint $$$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.
ExamplesInput6 1 1 1 2 2 1 1 2 2 3 4 6 2 4 1 5Output
4 3 3 4 1Input
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 12Output
10 2 10 4 9 9 2 6 2 3 4