A15574 · 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](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