出题需要树论
题号：NC317346
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一棵包含 n 个节点的树，树以 1 号节点为根。每个节点 i 都有一个点权 w_i。
\hspace{15pt}对于这棵树，定义它的美丽值为：所有从根节点到某个节点的路径中，路径上点权之和的最大值。形式化地，美丽值为：

\displaystyle\max_{1 \leqslant u \leqslant n}\sum_{v\in {\rm path}(1,u)}w_v

\hspace{15pt}其中 {\rm path}(1,u) 表示从根节点 1 到节点 u 的简单路径^\texttt{[1]}。
\hspace{15pt}现在你需要对这棵树恰好进行一次操作。每次操作可以选择一个节点 u，并将以 u 为根的子树^\texttt{[2]}中所有节点 v 的点权都变为 w_v\oplus x^\texttt{[3]}。
\hspace{15pt}请你求出恰好进行一次操作后，这棵树美丽值的最小可能值。

【名词解释】
\hspace{15pt}简单路径^\texttt{[1]}：图上从一个节点出发，经过若干条边到达另一个节点，且途中不重复经过任何节点的路径。
\hspace{15pt}子树^\texttt{[2]}：对于树中某个节点，其与所有后代节点构成的集合称为该节点的子树。
\hspace{15pt}\oplus^\texttt{[3]}：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqslant T\leqslant 10^4\right) 代表数据组数。每组测试数据描述如下：

\hspace{15pt}第一行输入两个整数 n,x\left(1\leqslant n\leqslant 2\times 10^5;\, 1\leqslant x<2^{30}\right)，分别表示树的节点数和异或参数。
\hspace{15pt}第二行输入 n 个整数 w_1,w_2,\dots,w_n\left(1\leqslant w_i<2^{30}\right)，表示每个节点的点权。
\hspace{15pt}接下来 n-1 行，每行输入两个整数 u,v\left(1\leqslant u,v\leqslant n;\, u\ne v\right)，表示树上的一条边。

\hspace{15pt}保证给出的图是一棵树，且所有测试数据中 n 的总和不超过 2 \times 10^5。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行输出一个非负整数，表示恰好进行一次操作后，这棵树美丽值的最小可能值。
示例1

输入

复制 
2
4 5
3 7 2 7
1 2
1 3
2 4
5 7
1 8 2 6 3
1 2
1 3
2 4
2 5

输出

复制 
7
12

备注: