Problem Description

Peppa and George are climbing a tree.

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

For each \( 1 \leq i \leq n \), output the number of pairs of nodes \((u, v)\) such that \( u < v \) and the path between \( u \) and \( v \) passes through all nodes with color \( i \), while other nodes (those not with color \( i \)) can be either passed through 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 exists an edge \((f_i, f_{i+1})\) in \( T \), and the sequence \(\{f\}\) contains no duplicate elements. It can be proven that for any pair of nodes \((u, v)\), there is a unique tree path.

Input Format

The first line contains a single positive integer \( n \).

The second line contains \( n \) positive integers, where the \( i \)-th integer represents \( w_i \).

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

Output Format

Output \( n \) lines, each containing a single positive integer. The \( i \)-th line should output the number of paths that include all nodes with color \( i \).

Sample Input and Output

Sample Input #1

4
1 2 2 3
1 2
2 3
3 4

Sample Output #1

3
4
3
6

Sample Input #2

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

Sample Output #2

45
35
9
0
1
45
34
9
17
45

Notes

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 are no nodes with color \( 4 \), all pairs satisfy the condition.

Data Range

For \( 40\% \) of the data, \( n \leq 10^2 \)

For \( 60\% \) of the data, \( n \leq 10^3 \)

For \( 100\% \) of the data, \( n \leq 10^6 \)

见题面 Input 部分

见题面 Output 部分