For a tree with $n$ vertices, color vertex $i$ with color $A_i$. Define $f(x, y)$ as the number of distinct colors on the simple path from $x$ to $y$. For each vertex $i$ from $1$ to $n$, calculate $\sum_{j=1}^{n} f(i, j)$.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
- The next $n-1$ lines each contain two integers $u, v$ indicating an edge between vertices $u$ and $v$.
### Output
- Output $n$ integers, where the $i$-th integer is $\sum_{j=1}^{n} f(i, j)$.
### Constraints
- $1 \le n, A_i \le 10^5$.
### Example
Input:
```
5
1 2 3 2 3
1 2
2 3
2 4
1 5
```
Output:
```
10
9
11
9
12
```
