Distinct Color Sum on Tree Paths

You are given a tree with n nodes, where each node is assigned a color. The colors are given as a sequence of n integers. For any two nodes i and j, define \(s(i,j)\) as the number of distinct colors on the unique simple path from node i to node j.

For each node i, define

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

Your task is to compute \(sum_i\) for every node \(i\) from 1 to \(n\).

Note: The tree is undirected. The input guarantees that the given edges form a tree.

inputFormat

The first line contains an integer \(n\) representing the number of nodes in the tree.

The second line contains \(n\) integers, where the \(i\)-th integer represents the color of node \(i\).

Each of the following \(n-1\) lines contains two integers \(u\) and \(v\), representing an edge between node \(u\) and node \(v\>.

outputFormat

Output \(n\) integers in one line. The \(i\)-th integer should be the value of \(sum_i\) for node \(i\) (1-indexed).

sample

3
1 2 1
1 2
2 3

5 5 5