Xor Path
题号：NC20857
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵n个点的树，每个点有权值。定义表示  到  的最短路径上，所有点的点权异或和。
对于，求所有的异或和。

输入描述:

第一行一个整数n。
接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。
第n+1行有n个整数，表示每个点的权值。

输出描述:

输出一个整数，表示所有的异或和，其中。
示例1

输入

复制 
4
1 2
1 3
1 4
1 2 3 4

输出

复制 
5

说明

{\mathbb{path}(1,2)=A_1\ \mathbb{xor}\ A_2=3\\<br />\mathbb{path}(1,3)=A_1\ \mathbb{xor}\ A_3=2\\<br />\mathbb{path}(1,4)=A_1\ \mathbb{xor}\ A_4=5\\<br />\mathbb{path}(2,3)=A_2\ \mathbb{xor}\ A_1\ \mathbb{xor}\ A_3=0\\<br />\mathbb{path}(2,4)=A_2\ \mathbb{xor}\ A_1\ \mathbb{xor}\ A_4=7\\<br />\mathbb{path}(3,4)=A_3\ \mathbb{xor}\ A_1\ \mathbb{xor}\ A_4=6}
再将这6个数异或起来就可以得到答案5了。

备注:

。