The Tree Has Fallen!

题意翻译

给定一棵 $n$ 个节点的无根树，每个节点有点权，$q$ 次询问，每次询问以 $r$ 为根，$v$ 的子树中任选若干个点点权异或和最大值。 $1\leq n,q\leq 2\times10^5$，$1\leq a_i\leq 10^9$。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

3
6
12 12 8 25 6 1
1 5
1 2
2 6
2 3
2 4
3
4 2
3 5
1 2
2
3 8
1 2
4
2 2
2 1
1 2
1 1
3
3 8 7
1 2
2 3
2
2 2
2 1

输出样例 #1

15
6
29
11
3
8
11
15
3

说明

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.

**题目大意**：

给定一棵无根树，树上有 $n$ 个节点，每个节点上都有一个整数值。现在有 $q$ 次询问，每次询问指定一个节点 $r$ 作为根节点，然后指定一个节点 $v$，要求从 $v$ 的子树中选取一些节点，使得这些节点上的值的异或和最大。

**输入输出数据格式**：

- **输入格式**：
- 第一行包含一个整数 $t$，表示测试用例的数量。
- 每个测试用例的第一行包含一个整数 $n$，表示树中节点的数量。
- 接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，分别表示每个节点上的值。
- 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。
- 下一行包含一个整数 $q$，表示询问的数量。
- 接下来 $q$ 行，每行包含两个整数 $r$ 和 $v$，分别表示指定的根节点和节点。

- **输出格式**：
- 对于每个测试用例，对于每个询问，输出一行，包含一个整数，表示最大的异或和。

**输入输出样例**：

- **输入样例**：
```
3
6
12 12 8 25 6 1
1 5
1 2
2 6
2 3
2 4
3
4 2
3 5
1 2
2
3 8
1 2
4
2 2
2 1
1 2
1 1
3
3 8 7
1 2
2 3
2
2 2
2 1
```

- **输出样例**：
```
15
6
29
11
3
8
11
15
3
```**题目大意**： 给定一棵无根树，树上有 $n$ 个节点，每个节点上都有一个整数值。现在有 $q$ 次询问，每次询问指定一个节点 $r$ 作为根节点，然后指定一个节点 $v$，要求从 $v$ 的子树中选取一些节点，使得这些节点上的值的异或和最大。 **输入输出数据格式**： - **输入格式**： - 第一行包含一个整数 $t$，表示测试用例的数量。 - 每个测试用例的第一行包含一个整数 $n$，表示树中节点的数量。 - 接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，分别表示每个节点上的值。 - 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。 - 下一行包含一个整数 $q$，表示询问的数量。 - 接下来 $q$ 行，每行包含两个整数 $r$ 和 $v$，分别表示指定的根节点和节点。 - **输出格式**： - 对于每个测试用例，对于每个询问，输出一行，包含一个整数，表示最大的异或和。 **输入输出样例**： - **输入样例**： ``` 3 6 12 12 8 25 6 1 1 5 1 2 2 6 2 3 2 4 3 4 2 3 5 1 2 2 3 8 1 2 4 2 2 2 1 1 2 1 1 3 3 8 7 1 2 2 3 2 2 2 2 1 ``` - **输出样例**： ``` 15 6 29 11 3 8 11 15 3 ```