Colorful Tree Paths

Given a tree \(T(V,E)\) with \(n\) nodes, each node \(i\) is assigned a color \(w_i\) satisfying \(1 \le w_i \le n\). The tree is undirected and there is a unique simple path between any two nodes. For each color \(i\) from \(1\) to \(n\), count the number of pairs of nodes \((u, v)\) with \(u < v\) such that the unique path from \(u\) to \(v\) passes through all nodes whose color is \(i\). For nodes with colors different from \(i\) the path can pass through them arbitrarily.

Note: The unique simple path between \(u\) and \(v\) is defined as a sequence of distinct nodes \(\{f_1, f_2, \dots, f_k\}\) where \(f_1 = u, f_k = v\), and for every \(1 \le j < k\), there is an edge \((f_j, f_{j+1})\) in \(T\).

Example: Consider a tree with 3 nodes and edges 1-2, 2-3, with colors: [1, 2, 1]. For color 1, the set of nodes is \(\{1, 3\}\). The only node pair (1, 3) has a path (1-2-3) that contains both node 1 and node 3, so the answer for color 1 is 1. For color 2, the only node is 2, and every path that passes node 2 is valid; there are 3 valid pairs in total. If a color does not appear in the tree, the answer for that color is 0.

inputFormat

The input begins with a single integer \(n\) (the number of nodes).

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) representing the colors of the nodes.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), indicating that there is an edge between nodes \(u\) and \(v\). The nodes are numbered from 1 to \(n\).

outputFormat

Output \(n\) integers. The \(i\)-th integer represents the number of node pairs \((u,v)\) with \(u < v\) such that the unique simple path from \(u\) to \(v)\) passes through all nodes of color \(i\). The answers for colors \(1\) to \(n\) should be output in order, separated by spaces.

sample

3
1 2 1
1 2
2 3

1 3 0