Description

Peppa and George are climbing a tree.

Given a tree $T(V,E)$ with $n$ nodes, the color of node $i$ is $w_i$, and it is guaranteed that $1 \leq w_i \leq n$.

For each $1 \leq i \leq n$, output how many pairs $(u,v)$ satisfy $u<v$, and the path from $u$ to $v$ passes through all nodes whose color is $i$. For other nodes whose color is not $i$, the path may pass through them or not.

A tree path $(u,v)$ is defined as a sequence $\{f\}$ such that $f_1=u$, $f_{|f|}=v$, and for all $1 \leq i < |f|$, there is an edge $(f_i,f_{i+1})$ in $T$, and there are no repeated elements in $\{f\}$. It can be proven that for any pair $(u,v)$, the tree path is unique.

Input Format

The first line contains one positive integer $n$.

The second line contains $n$ positive integers, where the $i$-th integer is $w_i$.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge $(u,v)$ in $T$.

Output Format

Output $n$ lines, each containing one positive integer. On the $i$-th line, output the number of paths that contain all nodes whose color is $i$.

4
1 2 2 3
1 2
2 3
3 4

3
4
3
6

10
9 7 4 2 3 4 4 5 8 5
2 1
3 2
4 2
5 2
6 4
7 4
8 1
9 4
10 4

45
35
9
0
1
45
34
9
17
45

Hint

For the first sample.

For color $1$, the pairs $(1,2),(1,3),(1,4)$ satisfy the condition.

For color $2$, the pairs $(1,3),(1,4),(2,3),(2,4)$ satisfy the condition.

For color $3$, the pairs $(1,4),(2,4),(3,4)$ satisfy the condition.

For color $4$, since there is no node with color $4$ in the graph, all pairs satisfy the condition.

Constraints

For $40\%$ of the testdata, $n \leq 10^2$.

For $60\%$ of the testdata, $n \leq 10^3$.

For $100\%$ of the testdata, $n \leq 10^6$.

Translated by ChatGPT 5