wxhtzdy ORO Tree
Contest: Codeforces Round 900 (Div. 3)
Difficulty rating: 2300
Tags: binary search, bitmasks, brute force, data structures, dfs and similar, implementation, trees

After (finally) qualifying for the IOI 2023, wxhtzdy was very happy, so he decided to do what most competitive programmers do: trying to guess the problems that will be on IOI. During this process, he accidentally made a problem, which he thought was really cool.

You are given a tree (a connected acyclic graph) with $$$n$$$ vertices and $$$n-1$$$ edges. Vertex $$$i$$$ ($$$1 \le i \le n$$$) has a value $$$a_i$$$.

Lets' define $$$g(u, v)$$$ as the bitwise or of the values of all vertices on the shortest path from $$$u$$$ to $$$v$$$. For example, let's say that we want to calculate $$$g(3, 4)$$$, on the tree from the first test case in the example. On the path from $$$3$$$ to $$$4$$$ are vertices $$$3$$$, $$$1$$$, $$$4$$$. Then, $$$g(3, 4) = a_3 \ | \ a_1 \ | \ a_4$$$ (here, $$$|$$$ represents the bitwise OR operation).

Also, you are given $$$q$$$ queries, and each query looks like this:

You are given $$$x$$$ and $$$y$$$. Let's consider all vertices $$$z$$$ such that $$$z$$$ is on the shortest path from $$$x$$$ to $$$y$$$ (inclusive).

Lets define the niceness of a vertex $$$z$$$ as the sum of the number of non-zero bits in $$$g(x, z)$$$ and the number of non-zero bits in $$$g(y, z)$$$. You need to find the maximum niceness among all vertices $$$z$$$ on the shortest path from $$$x$$$ to $$$y$$$.

Since his brain is really tired after solving an output only problem on SIO (he had to do it to qualify for the IOI), he wants your help with this problem.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices.

The second line of each test case contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_v \le 10^9$$$) — the value of each vertex, the $$$i$$$-th integer in this line corresponds to the vertex $$$i$$$.

Following $$$n - 1$$$ lines are the description of a tree.

Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$) — indicating that vertices $$$u$$$ and $$$v$$$ are connected by an edge.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — number of queries.

Following $$$q$$$ lines contain 2 integers $$$x, y$$$ ($$$1 \le x, y \le n$$$) — the vertices $$$x$$$ and $$$y$$$ for each query.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case output $$$q$$$ integers, each of which is the answer to the corresponding query.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
The image below shows the tree from the second example, first test case.

Tree from the second example, first test case

In the first query, we have $$$x=7$$$, $$$y=5$$$. The shortest path from $$$7$$$ to $$$5$$$ is $$$7-4-2-1-5$$$.

Let's calculate the niceness of vertex $$$7$$$ on this path. We have $$$g(7,7)=a_7=10=(1010)_2$$$ and $$$g(5,7)=a_5 \ | \ a_1 \ | \ a_2 \ | \ a_4 \ | \ a_7=10 \ | \ 4 \ | \ 7 \ | \ 4 \ | \ 10=15=(1111)_2$$$, so its niceness is equal to $$$2 + 4 = 6$$$.

Now let's calculate the niceness of vertex $$$4$$$ on this path. We have $$$g(7,4)=a_7 \ | \ a_4=10 \ | \ 4=14=(1110)_2$$$ and $$$g(5,4)=a_5 \ | \ a_1 \ | \ a_2 \ | \ a_4=10 \ | \ 4 \ | \ 7 \ | \ 4=15=(1111)_2$$$, so its niceness is equal to $$$3 + 4 = 7$$$.

Now let's calculate the niceness of vertex $$$2$$$ on this path. We have $$$g(7,2)=a_7 \ | \ a_4 \ | \ a_2=10 \ | \ 4 \ | \ 7=15=(1111)_2$$$ and $$$g(5,2)=a_5 \ | \ a_1 \ | \ a_2=10 \ | \ 4 \ | \ 7=15=(1111)_2$$$, so its niceness is equal to $$$4 + 4 = 8$$$.

Now let's calculate the niceness of vertex $$$1$$$ on this path. We have $$$g(7,1)=a_7 \ | \ a_4 \ | \ a_2 \ | \ a_1=10 \ | \ 4 \ | \ 7 \ | \ 4=15=(1111)_2$$$ and $$$g(5,1)=a_5 \ | \ a_1=10 \ | \ 4=14=(1110)_2$$$, so its niceness is equal to $$$4 + 3 = 7$$$.

Finally, let's calculate the niceness of vertex $$$5$$$ on this path. We have $$$g(7,5)=a_7 \ | \ a_4 \ | \ a_2 \ | \ a_1 \ | \ a_5=10 \ | \ 4 \ | \ 7 \ | \ 4 \ | \ 10=15=(1111)_2$$$ and $$$g(5,5)=a_5=10=(1010)_2$$$, so its niceness is equal to $$$4 + 2 = 6$$$.

The maximum niceness on this path is at vertex $$$2$$$, and it is $$$8$$$.

Example input:
3
4
1 2 3 4
1 3
1 2
1 4
3
1 1
1 3
1 4
3
7 6 3
3 1
2 1
4
1 1
1 2
1 3
2 3
1
4
1
1 1

Example output:
2 4 3 
6 6 6 6 
2

Example input:
3
7
4 7 7 4 10 8 10
6 1
3 1
2 1
7 4
1 5
4 2
4
7 5
2 3
4 5
2 5
6
9 5 6 2 4 6
5 1
2 1
1 6
4 3
1 3
4
6 1
1 4
4 3
3 5
7
5 1 3 7 5 1 6
2 1
5 4
2 3
3 4
7 6
6 3
2
4 2
7 7

Example output:
8 6 7 7 
6 6 4 7 
6 4

Editorial:
Observation 1: it's enough to only consider $$$2 \cdot \log(max(a))$$$ vertices on the shortest path from $$$x$$$ to $$$y$$$ as candidates for $$$z$$$ for each query. Why? Because at most $$$\log(max(a))$$$ vertices can add a bit to $$$g(x, z)$$$ and we only need to maximize the number of bits in $$$g(x, z)$$$ + the number of bits in $$$g(y, z)$$$, and all the other vertices will not contribute to the sum at all so we don't even need to consider them for $$$z$$$.
Now we need to find those vertices. We know that for each bit, the vertex which we will consider can give this bit to $$$g(x, z)$$$ will be the closest one to vertex $$$x$$$ (on the path from $$$x$$$ to $$$y$$$).
How do we find these vertices qucikly? First let's arbitrarily root the tree. Now let's precalculate for each vertex and bit $$$cnt[vertex][bit]$$$ as the number of vertices on the path from the root to this vertex which have this bit set in their value. Then for each bit, we can binary search to find it's first occurenece on the path from $$$x$$$ to $$$y$$$, and the path from $$$y$$$ to $$$x$$$.
We do binary search by taking $$$mid$$$ from vertex $$$x$$$ to vertex $$$y$$$ and calculating the number of vertices which have the current bit set, by using the $$$cnt$$$ matrix combined with range minimum query or binary lifting to find the lowest common ancestor. We are searching for the first position where the number of those is >0. Once we find all the vertices, we can for each of those, in $$$O(log(max(a))$$$, calculate it's niceness, and take the maximum out of those.
Time complexity: $$$O(q \cdot (\log n + \log(max(a)) \cdot \log n)$$$.