Colorful Trees

Time limit1sMemory limit1024 MB

Summary

For each edge of a vertex-colored tree, count the same-color vertex pairs whose connecting path passes through that edge.

Level: Medium7 of 10
Topics: Tree, Hash map, DFS
Solved: No attempts yet

Problem

You are given a tree whose vertices are colored. For each edge, count the pairs of vertices with the same color whose path between them contains that edge. Since the graph is a tree, every pair of vertices is joined by exactly one path.

Input

The first line contains a single integer $n$ ( $2 \le n \le 10^5$ ), the number of vertices. The vertices are numbered from 1 to $n$ .

Each of the next $n$ lines contains a single integer $c$ ( $1 \le c \le n$ ), the color of each vertex in order.

Each of the next $n-1$ lines contains two integers $a$ and $b$ ( $1 \le a < b \le n$ ), denoting an undirected edge between vertices $a$ and $b$ .

Output

Output $n-1$ lines. Each line contains one integer, the answer for the edge at the corresponding position in the input, in input order.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
4
2
2
2
2
3 4
2 4
1 2
```
Expected output
```
3
4
3
```