题目描述
给定一个包含 $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$。