P5593 小猪佩奇爬树 加强版

CYJian 在打 洛谷 10 月月赛I Div. 2 的时候，用一种 $O(N)$ 的做法过了这道题的原题。 但是好像这题是可以给常数小的 $O(N \log N)$ 甚至 $O(N^2)$ 过的。 CYJian 觉得很不服并且出了这道加强版。 --- 因为有人反馈 `OLE` 的问题，所以 CYJian 将输出改为原来所有输出的异或和。

原题数据可能过水，有些错误的做法也可以过原来的题目。**所以可能原题能过在这里就WA了。** ~~比如我自己原来一个错解也过了，一堆东西没考虑。~~ 样例解释部分可以参见 [P5588](https://www.luogu.org/problem/P5588)。 一句话题意：给出一棵 $n$ 个点的树，每个点上有一种颜色，请你求出对于每一种颜色，树上有多少条链包含该种颜色的所有点。 注意下面的数据范围。**请注意常数因子对程序效率的影响。** 如果需要请使用 [IO优化](https://www.luogu.org/paste/i11c3ppx)

输入文件共 $n + 1$ 行。 第一行一个正整数 $n$ 表示树的节点数。 接下来一行 $n$ 个正整数，第 $i$ 个正整数表示编号为 $i$ 的节点的颜色。颜色范围在 $[1, n]$ 内。 接下来 $n - 1$ 行，每行两个正整数表示一条树边。

输出文件应该包括 $1$ 行。 令编号为 $i$ 的颜色的权值为满足题目条件的链的数量。**注意若存在一种颜色满足没有任何一个点属于该颜色，这种颜色的权值为** $\frac{n \times (n - 1)}{2}$ 你仅需要输出所有 $n$ 种颜色的权值异或和。

一共 $5$ 组数据，第 $i$ 组的数据范围： $n = 3 \times 10^{i+1}$