Description

lrb has a tree, and each node has a color. Given a color sequence of length $n$, define $s(i, j)$ as the number of distinct colors on the simple path from node $i$ to node $j$.

$$sum_i=\sum_{j=1}^n s(i, j)$$

Now he wants you to compute all $sum_i$.

For $40\%$ of the testdata, $n \leq 2000$. For $100\%$ of the testdata, $1 \leq n, c_i \leq 10^5$.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

The second line contains $n$ integers, the colors of the $n$ nodes: $c_1, c_2, \ldots, c_n$.

Each of the next $n-1$ lines contains two integers $x, y$, meaning there is an edge between $x$ and $y$.

Output Format

Output $n$ lines. The $i$-th line should be $sum_i$.

5
1 2 3 2 3
1 2
2 3
2 4
1 5

10
9
11
9
12

Hint

$$sum_1=s(1,1)+s(1,2)+s(1,3)+s(1,4)+s(1,5)=1+2+3+2+2=10$$$$sum_2=s(2,1)+s(2,2)+s(2,3)+s(2,4)+s(2,5)=2+1+2+1+3=9$$$$sum_3=s(3,1)+s(3,2)+s(3,3)+s(3,4)+s(3,5)=3+2+1+2+3=11$$$$sum_4=s(4,1)+s(4,2)+s(4,3)+s(4,4)+s(4,5)=2+1+2+1+3=9$$$$sum_5=s(5,1)+s(5,2)+s(5,3)+s(5,4)+s(5,5)=2+3+3+3+1=12$$

Translated by ChatGPT 5