406058: GYM102253 C Colorful Tree

There is a tree having $$$n$$$ nodes, the $$$i$$$-th node of which has a type of color, denoted by an integer $$$c_i$$$.

The path between every two nodes is unique, of which we define the value is the number of distinct types of colors appearing on it.

Calculate the sum of values of all possible paths, $$$\frac{n (n - 1)}{2}$$$ in total, between two different nodes on the tree.

The input contains multiple (about $$$50$$$) test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$), indicating the number of nodes.

The next line contains $$$n$$$ integers, the $$$i$$$-th number of which is $$$c_i$$$ ($$$1 \leq c_i \leq n$$$), denoting the color of the $$$i$$$-th node.

Each of the next $$$(n - 1)$$$ lines contains two integers $$$x$$$, $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$), representing an edge between the $$$x$$$-th node and the $$$y$$$-th one. It is guaranteed that given edges form a tree.

For each test case, output "Case #x: y" in one line (without quotes), where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ denotes the answer to the corresponding case.

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

Case #1: 6
Case #2: 29