题目背景

CYJian 在打 洛谷 10 月月赛I Div. 2 的时候，用一种 $O(N)$ 的做法过了这道题的原题。

但是好像这题是可以给常数小的 $O(N \log N)$ 甚至 $O(N^2)$ 过的。 CYJian 觉得很不服并且出了这道加强版。

因为有人反馈 OLE 的问题，所以 CYJian 将输出改为原来所有输出的异或和。

题目描述

原题数据可能过水，有些错误的做法也可以过原来的题目。所以可能原题能过在这里就WA了。

比如我自己原来一个错解也过了，一堆东西没考虑。

样例解释部分可以参见 P5588。

一句话题意：给出一棵 $n$ 个点的树，每个点上有一种颜色，请你求出对于每一种颜色，树上有多少条链包含该种颜色的所有点。

注意下面的数据范围。请注意常数因子对程序效率的影响。

如果需要请使用 IO优化

输入格式

输入文件共 $n + 1$ 行。

第一行一个正整数 $n$ 表示树的节点数。

接下来一行 $n$ 个正整数，第 $i$ 个正整数表示编号为 $i$ 的节点的颜色。颜色范围在 $[1, n]$ 内。

接下来 $n - 1$ 行，每行两个正整数表示一条树边。

输出格式

输出文件应该包括 $1$ 行。

令编号为 $i$ 的颜色的权值为满足题目条件的链的数量。注意若存在一种颜色满足没有任何一个点属于该颜色，这种颜色的权值为 $\frac{n \times (n - 1)}{2}$

你仅需要输出所有 $n$ 种颜色的权值异或和。

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

提示

一共 $5$ 组数据，第 $i$ 组的数据范围：

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