P7310 [COCI 2018/2019 #2] Deblo

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

第一行输入正整数 $N$，表示树的结点个数。 第二行输入 $N$ 个用空格分隔的整数 $v_i$，第 $i$ 个整数表示结点 $i$ 的权值。 接下来的 $N-1$ 行，每行输入整数 $a_j,b_j$，表示 $a_j,b_j$ 之间有一条边。

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

#### 样例 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$。 #### 说明 **本题分值按 COCI 原题设置，满分 $90$。** **题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf) _T3 Deblo_。**