题目描述

给定一个包含 $n$ 个结点的树，其中每个结点都有一个权值。一条路径的权值定义为该路径经过的所有结点的权值异或后的结果。

你的任务是求出所有路径的权值之和。

输入格式

第一行输入正整数 $N$，表示树的结点个数。

第二行输入 $N$ 个用空格分隔的整数 $v_i$，第 $i$ 个整数表示结点 $i$ 的权值。

接下来的 $N-1$ 行，每行输入整数 $a_j,b_j$，表示 $a_j,b_j$ 之间有一条边。

输出格式

输出所有路径的权值之和。

样例 #1

样例输入 #1

3
1 2 3
1 2
2 3

样例输出 #1

10

样例 #2

样例输入 #2

5
2 3 4 2 1
1 2
1 3
3 4
3 5

样例输出 #2

64

样例 #3

样例输入 #3

6
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6

样例输出 #3

85

提示

样例 1 解释

路径 $1 \to 1$ 的权值为 $1$；

路径 $1 \to 2$ 的权值为 $1⊕2=3$；

路径 $1 \to 3$ 的权值为 $1⊕2⊕3=0$；

路径 $2 \to 2$ 的权值为 $2$；

路径 $2 \to 3$ 的权值为 $2⊕3=1$；

路径 $3 \to 3$ 的权值为 $3$。

所有路径的权值之和为 $1+3+0+2+1+3=10$。

数据规模与约定

对于 $30\%$ 的数据，$N \le 200$。

对于 $50\%$ 的数据，$N \le 1000$。

对于另外 $20\%$ 的数据，$x=1,2,\cdots,N-1$ 中的每个结点都和结点 $x+1$ 之间有一条边。

对于 $100\%$ 的数据，$1 \le a_j,b_j \le N \le 10^5$，$0 \le v_i \le 3 \times 10^6$。