The Tree Has Fallen!
Contest: Codeforces Round 848 (Div. 2)
Difficulty rating: 2500
Tags: bitmasks, dfs and similar, math, trees

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

Input format:
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$$$.

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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.

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.

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.

Example input:
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

Example output:
15
6
29
11
3
8
11
15
3

Editorial:
At first, we can think of another problem. Given an array. You need to find the maximum subset $$$XOR$$$. How can we solve it? We can solve this problem very efficiently using a technique called "$$$XOR$$$ Basis". You can read about it from here.
In problem E, at first, we can fix any node as the root of the tree. Let's call this rooted tree the base tree. After that, start an Euler tour from the root and assign discovery time $$$d_u$$$ and finishing time $$$f_u$$$ to each node $$$u$$$. In each query, three types of cases can occur (node $$$r$$$ and node $$$v$$$ are from the query format):
1. $$$r=v$$$. In this case, we need to calculate the maximum subset $$$XOR$$$ of the whole tree.
2. Node $$$v$$$ is not an ancestor of node $$$r$$$ in the base tree. So, the subtree of node $$$v$$$ will remain the same.
3. Node $$$v$$$ is an ancestor of node $$$r$$$ in the base tree. What will be the new subtree of node $$$v$$$ in this case? This is a bit tricky. Let's denote such a node $$$c$$$ that is a child of node $$$v$$$ and an ancestor of node $$$r$$$ in the base tree. Then the new subtree of node $$$v$$$ will contain the whole tree except the subtree (in the base tree) of node $$$c$$$.
Let's say, $$$in_u$$$ is the $$$XOR$$$ basis of all the values in node $$$u$$$'s subtree (in the base tree). We can build $$$in_u$$$ by inserting the value $$$a_u$$$ to $$$in_u$$$ and merging it with all of its children $$$w$$$'s basis $$$in_w$$$. Two basis can be merged in $$$O(log^2(d))$$$ complexity, where $$$d$$$ is their dimension. If we can build the basis $$$in_u$$$ for each node $$$u$$$, we are able to answer the case $$$1$$$ and case $$$2$$$. To answer case $$$2$$$, we need to find the maximum subset $$$XOR$$$ in the corresponding basis. To answer case $$$1$$$, we need to do a similar thing in the basis $$$in_{root}$$$, where $$$root$$$ is the root node of the base tree.
For case $$$3$$$, let's say $$$out_u$$$ is the $$$XOR$$$ basis of all the values of the base tree except the node $$$u$$$'s subtree (in the base tree). Then the answer of the case $$$3$$$ will be the maximum subset $$$XOR$$$ in the basis $$$out_c$$$. To build the basis $$$out_u$$$ for each node $$$u$$$, we can utilize the properties of the discovery time $$$d_u$$$ and finishing time $$$f_u$$$. Which nodes will be outside the subtree of node $$$u$$$? The nodes $$$w$$$ that have either $$$d_w < d_u$$$ or $$$d_w > f_u$$$. To merge their basis easily, we can pre-calculate two basis arrays $$$pre[]$$$ and $$$suf[]$$$ where the basis $$$pre_i$$$ includes all the values of the nodes $$$w$$$ such that $$$d_w \leq i$$$ and the basis $$$suf_i$$$ includes all the values of the nodes $$$w$$$ such that $$$d_w \geq i$$$.
To find the node $$$c$$$ in the case $$$3$$$, we can perform a binary search on the children of node $$$v$$$. We can use the fact that the order of the discovery times follows the order of the children and a node $$$c$$$ is only an ancestor of a node $$$r$$$ iff $$$d_c \leq d_r$$$ && $$$f_c \geq f_r$$$.
Time complexity: $$$\mathcal{O}(n\times log^2(d))$$$, where $$$d = max(a_i)$$$