P5593 Peppa Pig Climbing Trees (Enhanced Version).

When CYJian was doing Luogu October Monthly Contest I Div. 2, they solved the original version of this problem with an $O(N)$ approach. But it seems this problem can be passed with a small-constant $O(N \log N)$ or even $O(N^2)$ solution. CYJian felt unconvinced and made this enhanced version. --- Because someone reported an `OLE` issue, CYJian changed the output to the XOR sum of all original outputs.

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](https://www.luogu.org/problem/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](https://www.luogu.org/paste/i11c3ppx).

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.

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.

There are $5$ test groups. For the $i$-th group, the Constraints are: $n = 3 \times 10^{i+1}$ Translated by ChatGPT 5