又一树上异或和
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一棵由 n 个节点构成的树,每一个点都有其对应的乐趣值 a_i
\hspace{15pt}对于树上的任意一条路径(可以不是简单路径),记这条路径上所有点的乐趣值的异或和为这条路径的“总乐趣值”。注意,如果一个点多次经过,那么这个点的乐趣值要参与多次异或运算。
\hspace{15pt}XiaoT 想要从中制定旅行方案,于是他进行了 q 次询问,对于每次询问:
\hspace{15pt}选择起点 a 和终点 b,请你告诉他以点 a 为起点,点 b 为终点的所有路径中,能得到的最大“总乐趣值”是多少。这里的路径不一定是简单路径,同时也不一定要到达 a 点或 b 点后立刻停止。

输入描述:

\hspace{15pt}第一行输入两个正整数 n,q \left(1\le n \le 10^5;\ 1\le q\le 2\times 10^5\right) 代表树上的节点数量、询问次数。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(0\le a_i\lt 2^{31}\right) 代表每个点的乐趣值。
\hspace{15pt}此后 n-1 行,第 i 行输入两个正整数 u_i,v_i \left(1\le u_i,v_i\le n\right) 代表树上的第 i 条边连接节点 u_i 和节点 v_i
\hspace{15pt}此后 q 行,每行输入两个正整数 a,b \left(1\le a,b\le n\right) 代表一次询问。

输出描述:

\hspace{15pt}对于每一次询问,新起一行。输出一个整数,代表最大的“总乐趣值”。
示例1

输入

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

输出

复制
3
3

说明

\hspace{15pt}在这个样例中,树的形状如下图所示。我们使用 \oplus 表示异或运算。
alt text\hspace{15pt}
    对于第一次查询,其中一种可行的路径是 2\to 1\to 2\to 1\to 3,答案计算为 a_2 \oplus a_1 \oplus a_2 \oplus a_1 \oplus a_3 = 3
\hspace{15pt}对于第二次查询,其中一种可行的路径是 2\to 1\to 3\to 4\to 3\to 5 ,答案计算为 a_2 \oplus a_1 \oplus a_3 \oplus a_4 \oplus a_3 \oplus a_5 = 3
示例2

输入

复制
4 3
1 3 5 17
1 2
2 3
3 4
1 4
2 3
4 2

输出

复制
22
22
23