Problem D
Colorful Trees
Given a tree with colored vertices, for each edge, how many pairs of vertices with the same color have that edge on the path between them? Note that since it’s a tree, each pair of nodes has exactly one path between them.
Input
The first line of input contains a single integer
Each of the next
Each of the next
Output
Output
Sample Input 1 | Sample Output 1 |
---|---|
6 3 1 2 1 2 2 2 6 4 5 1 4 3 4 1 2 |
2 2 3 2 3 |
Sample Input 2 | Sample Output 2 |
---|---|
4 2 2 2 2 3 4 2 4 1 2 |
3 4 3 |