CF1778E.The Tree Has Fallen!

Recently, a tree has fallen on Bob's head from the sky. The tree has $n$ nodes. Each node $u$ of the tree has an integer number $a_u$ written on it. But the tree has no fixed root, as it has fallen from the sky.

Bob is currently studying the tree. To add some twist, Alice proposes a game. First, Bob chooses some node $r$ to be the root of the tree. After that, Alice chooses a node $v$ and tells him. Bob then can pick one or more nodes from the subtree of $v$. His score will be the bitwise XOR of all the values written on the nodes picked by him. Bob has to find the maximum score he can achieve for the given $r$ and $v$.

As Bob is not a good problem-solver, he asks you to help him find the answer. Can you help him? You need to find the answers for several combinations of $r$ and $v$ for the same tree.

Recall that a tree is a connected undirected graph without cycles. The subtree of a node $u$ is the set of all nodes $y$ such that the simple path from $y$ to the root passes through $u$. Note that $u$ is in the subtree of $u$.

最近，一棵树从天而降，砸在了 Bob 的头上。这棵树有 $n$ 个节点。树中每个节点 $u$ 上都写有一个整数 $a_u$。但由于这棵树是从天上掉下来的，因此它没有固定的根节点。

Bob 正在研究这棵树。为了增添一些趣味性，Alice 提出了一个游戏：首先，Bob 任选一个节点 $r$ 作为树的根；接着，Alice 选定一个节点 $v$ 并告诉 Bob；然后，Bob 可以从节点 $v$ 的子树中选取一个或多个节点；他的得分为所选节点上所有数值的按位异或（XOR）（参见按位运算#异或）。对于给定的 $r$ 和 $v$，Bob 需要找出他所能获得的最大得分。

由于 Bob 不擅长解题，他请你帮忙找出答案。你能帮他吗？你需要对同一棵树的多组 $(r, v)$ 组合分别求出对应答案。

注意：树是一种无环的连通无向图。节点 $u$ 的子树定义为所有满足“从 $y$ 到根节点的简单路径经过 $u$”的节点 $y$ 所构成的集合。特别地，$u$ 自身属于其自身的子树。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line contains an integer $n$ ($2\leq n\leq 2 \cdot 10^5$) — the number of nodes of the tree.

The next line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1\leq a_i\leq 10^9$) — the values written on the nodes.

Each of the next $n-1$ lines contain two integers $u$ and $v$ ($1\leq u, v\leq n$; $u\neq v$), denoting there is an undirected edge between node $u$ and node $v$. It is guaranteed that the given edges form a tree.

The next line contains an integer $q$ ($1\leq q\leq 2 \cdot 10^5$) — the number of queries.

Each of the next $q$ lines contains two integers $r$ and $v$ ($1\leq r, v\leq n$) — the root node Bob defines, and the node Alice chooses.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases don't exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, in each query, print a line containing an integer denoting the maximum score Bob can achieve.

对于每个测试用例，在每次查询中，输出一行，包含一个整数，表示 Bob 能够获得的最大得分。

In each of the below figures, the green-colored node is the node picked by Bob, and the red-colored node is the node picked by Alice. The values of the nodes are placed in the blue boxes beside the nodes.

Consider the first example. In the first query, if we put the root node $4$ at the top of the tree, the tree looks like the below figure:

Tree with root node $4$ in the first query.

The nodes in the subtree of the node $2$ are $[2,1,5,6,3]$. Among them, Bob can pick node $3$, node $5$, and node $6$. His score will be $a_3 \oplus a_5 \oplus a_6 = 8 \oplus 6 \oplus 1 = 15$. He can't achieve any score more than this.

In the second query, if the root node $3$ is placed at the top of the tree, the tree looks like the below figure:

Tree with root node $3$ in the second query.

The only node in the subtree of the node $5$ is $5$. Bob can only pick the node $5$. His score will be $a_5 = 6$.

In the third query, if the root node $1$ is placed at the top of the tree, the tree looks like this:

Tree with root node $1$ in the third query.

The nodes in the subtree of the node $2$ are $[2,3,6,4]$. Among them, Bob can pick node $2$, node $3$, and node $4$. His score will be $a_2 \oplus a_3 \oplus a_4 = 12 \oplus 8 \oplus 25 = 29$. He is not able to score higher than that.

在以下每个图中，绿色节点表示 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$。他无法获得高于此值的得分。