Description

The testdata of the original problem might be too weak, so some incorrect solutions could also pass the original problem. So a solution that passes the original problem may get WA here.

For example, one of my wrong solutions also passed before, because I did not consider a lot of things.

For the sample explanation, you can refer to P5588.

One-sentence statement: Given a tree with $n$ nodes, each node has a color. For each color, compute how many paths (chains) in the tree contain all nodes of that color.

Pay attention to the Constraints below. Please pay attention to how constant factors affect program efficiency.

If needed, please use I/O optimization.

Input Format

The input file has $n + 1$ lines in total.

The first line contains a positive integer $n$, the number of nodes in the tree.

The next line contains $n$ positive integers. The $i$-th positive integer represents the color of node $i$. The color range is within $[1, n]$.

The next $n - 1$ lines each contain two positive integers describing an edge of the tree.

Output Format

The output file should contain $1$ line.

Let the weight of color $i$ be the number of paths (chains) that satisfy the condition in the statement. Note that if there exists a color such that no node has this color, then the weight of this color is $\frac{n \times (n - 1)}{2}$.

You only need to output the XOR sum of the weights of all $n$ colors.

4
1 2 2 3
1 2
2 3
3 4

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

60

Hint

There are $5$ test groups. For the $i$-th group, the Constraints are:

$n = 3 \times 10^{i+1}$

Translated by ChatGPT 5