Background

CYJian encountered and solved the original version of this problem during the October Monthly Contest I Div. 2 on Luogu with an $O(N)$ approach.

However, it seems that this problem can also be solved by $O(N \log N)$ or even $O(N^2)$ algorithms with small constants. CYJian felt unsatisfied and created this enhanced version.

Due to feedback about OLE issues, CYJian has modified the output to be the XOR sum of all original outputs.

Problem Description

The original problem's data might be too weak, allowing incorrect solutions to pass. Therefore, solutions that passed the original problem might fail here.

For example, my own incorrect solution passed the original problem, missing many considerations.

For sample explanations, refer to P5588.

In a nutshell: Given a tree with $n$ nodes, each node has a color. Your task is to determine, for each color, how many paths in the tree include all nodes of that color.

Pay attention to the data range below. Be mindful of the impact of constant factors on program efficiency.

If needed, use IO optimization.

Input Format

The input file consists of $n + 1$ lines.

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

The next line contains $n$ positive integers, where the $i$-th integer represents the color of the node with the number $i$. The color ranges from $[1, n]$.

The following $n - 1$ lines each contain two positive integers representing an edge in the tree.

Output Format

The output file should include one line.

Let the weight of the color with number $i$ be the number of paths that satisfy the conditions of the problem. Note that if a color has no nodes of that color, its weight is $\frac{n \times (n - 1)}{2}$.

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

Sample Input and Output

Input Sample #1

4
1 2 2 3
1 2
2 3
3 4

Output Sample #1

2

Input Sample #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

Output Sample #2

60

Notes

There are 5 sets of data, with the $i$-th set having the following data range:

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

见题面 Input 部分

见题面 Output 部分