CF1778E The Tree Has Fallen!

最近，一棵树从天而降，砸在了 Bob 的头上。这棵树有 $n$ 个节点。树上的每个节点 $u$ 上都写有一个整数 $a_u$。但由于树是从天上掉下来的，所以没有固定的根节点。 Bob 正在研究这棵树。为了增加趣味性，Alice 提出了一个游戏。首先，Bob 选择某个节点 $r$ 作为树的根节点。之后，Alice 选择一个节点 $v$ 并告诉 Bob。然后，Bob 可以从 $v$ 的子树中选择一个或多个节点。他的得分将是他所选节点上所有数字的按位异或（bitwise XOR）结果。对于给定的 $r$ 和 $v$，Bob 需要找出他能获得的最大得分。 由于 Bob 不是一个擅长解题的人，他请求你帮他找到答案。你能帮他吗？你需要针对同一棵树的多组 $r$ 和 $v$ 组合进行解答。 请注意，树是一种无环连通无向图。节点 $u$ 的子树是所有满足从 $y$ 到根的简单路径经过 $u$ 的节点 $y$ 的集合。注意 $u$ 也属于 $u$ 的子树。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^5$）。接下来是每个测试用例的描述。 第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示树的节点数。 下一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示每个节点上的值。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$；$u \neq v$），表示在节点 $u$ 和节点 $v$ 之间有一条无向边。保证给定的边构成一棵树。 下一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$），表示询问的数量。 接下来的 $q$ 行，每行包含两个整数 $r$ 和 $v$（$1 \leq r, v \leq n$），分别表示 Bob 选定的根节点和 Alice 选定的节点。 保证所有测试用例中 $n$ 的总和与 $q$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例的每个询问，输出一行一个整数，表示 Bob 能获得的最大得分。

下图中，绿色节点为 Bob 选择的节点，红色节点为 Alice 选择的节点。节点的值显示在节点旁的蓝色框中。 考虑第一个示例。在第一个询问中，如果我们将根节点 $4$ 放在树的顶部，树的结构如下图所示：  第一个询问中以节点 $4$ 为根的树。节点 $2$ 的子树为 $[2,1,5,6,3]$。在这些节点中，Bob 可以选择节点 $3$、节点 $5$ 和节点 $6$。他的得分为 $a_3 \oplus a_5 \oplus a_6 = 8 \oplus 6 \oplus 1 = 15$。他无法获得更高的分数。 在第二个询问中，如果将根节点 $3$ 放在树的顶部，树的结构如下图所示：  第二个询问中以节点 $3$ 为根的树。节点 $5$ 的子树只有 $5$。Bob 只能选择节点 $5$，得分为 $a_5 = 6$。 在第三个询问中，如果将根节点 $1$ 放在树的顶部，树的结构如下图所示：  第三个询问中以节点 $1$ 为根的树。节点 $2$ 的子树为 $[2,3,6,4]$。在这些节点中，Bob 可以选择节点 $2$、节点 $3$ 和节点 $4$。他的得分为 $a_2 \oplus a_3 \oplus a_4 = 12 \oplus 8 \oplus 25 = 29$。他无法获得更高的分数。 由 ChatGPT 4.1 翻译