Counting Colorful Chains in a Tree

You are given a tree with n nodes. Each node is assigned a color. A chain is defined as the unique simple path between two distinct nodes in the tree. For each color that appears in the tree, you are to count the number of chains (i.e. unordered pairs of distinct nodes) whose unique simple path contains all the nodes of that color.

Important note: It is possible that some wrong approaches would pass the original data but will fail on these test cases. Also, constant‐factor optimization (for example, using fast I/O methods) might be required.

For example, if the nodes of a given color do not all lie on some common simple path then the answer for that color is 0. Otherwise, assume the nodes of that color are collinear; let L and R be the two endpoints of the unique minimal path covering all nodes of that color. Then any chain whose endpoints come from the two "extensions" of L and R (in the directions away from the unique neighbor on the chain) will contain all nodes of that color. More precisely:

• If the set of nodes of the color has size one (say, only vertex v), then the answer is the number of chains that contain v. This can be computed by considering the connected components created when removing v from the tree. Namely, if the sizes of these components are \(a_1, a_2, \ldots, a_k\), then the answer is \[ \binom{n}{2} - \sum_{i=1}^{k} \binom{a_i}{2}. \]
• If the set of nodes has size at least two, choose an arbitrary node x in the set, and let y be the farthest node (in terms of number of edges) from x among the nodes of that color. Then let L=y and let R be the node farthest from y among the nodes in the set. It can be shown that all nodes in the set lie on the unique simple path from L to R if and only if for every node w in the set
  \( d(L,R)=d(L, w)+d(w,R) \). Otherwise, the answer is 0 for that color. If they are collinear, let nxt(L) be the unique neighbor of L on the L-to-R path and nxt(R) the unique neighbor of R on the R-to-L path. Define the extension count for L as the number of vertices in the connected component of L when the edge (L, nxt(L)) is removed. (That is, if L is a child of nxt(L) in a fixed DFS tree then the count is the size of the subtree of L otherwise it is \(n-\text{size}(nxt(L))\). The value for R is defined similarly.) The answer for that color is the product of the two extension counts.

See P5588 for a sample explanation.

inputFormat

The first line contains a single integer n (2 ≤ n ≤ 10⁵), the number of nodes in the tree.

The second line contains n integers \(c_1, c_2, \ldots, c_n\) (1 ≤ \(c_i\) ≤ 10⁹), where \(c_i\) is the color of the \(i\)-th node.

Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) indicating that there is an edge between nodes u and v.

It is guaranteed that the given graph is a tree.

outputFormat

For each distinct color that appears in the tree, output a line containing two integers: the color and the corresponding number of chains that contain all nodes of that color. The output should be sorted in increasing order by color.

sample

5
1 2 1 2 1
1 2
2 3
2 4
3 5

1 3
2 2