CF1878G.wxhtzdy ORO Tree

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.

在（终于）获得 IOI 2023 参赛资格后，wxhtzdy 非常开心，于是决定做大多数竞赛程序员都会做的事：尝试猜测 IOI 上可能出现的题目。在此过程中，他意外地构造出了一道题，并认为这道题非常酷。

你将得到一棵树（一个连通无环图），该树包含 $n$ 个顶点和 $n-1$ 条边。顶点 $i$（$1 \le i \le n$）具有一个权值 $a_i$。

我们定义 $g(u, v)$ 为从 $u$ 到 $v$ 的最短路径上所有顶点的权值的按位或（bitwise OR）。例如，在样例的第一个测试用例所给的树中，若要计算 $g(3, 4)$，则从 $3$ 到 $4$ 的路径上的顶点依次为 $3$、$1$、$4$，因此 $g(3, 4) = a_3 \ | \ a_1 \ | \ a_4$（此处 $|$ 表示按位或运算）。

此外，你还会得到 $q$ 个查询，每个查询的形式如下：

给定 $x$ 和 $y$。考虑所有位于从 $x$ 到 $y$ 的最短路径上的顶点 $z$（含端点）。

我们定义顶点 $z$ 的**优美度（niceness）**为：$g(x, z)$ 的二进制表示中非零位的个数，加上 $g(y, z)$ 的二进制表示中非零位的个数。你需要找出所有满足条件的 $z$（即所有在 $x$ 到 $y$ 最短路径上的顶点）中，最大的优美度。

由于他在 SIO 上刚解完一道“仅输出”类题目（他必须完成该题才能获得 IOI 参赛资格），大脑已极度疲惫，因此希望你能帮他解决这个问题。

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

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——顶点的数量。

每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_v \le 10^9$）——每个顶点的权值，该行中第 $i$ 个整数对应顶点 $i$。

接下来的 $n - 1$ 行描述一棵树。

每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n,\ u \ne v$）——表示顶点 $u$ 和 $v$ 之间有一条边相连。

下一行包含一个整数 $q$（$1 \le q \le 10^5$）——查询的数量。

接下来的 $q$ 行每行包含两个整数 $x, y$（$1 \le x, y \le n$）——表示每次查询所涉及的顶点 $x$ 和 $y$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

保证所有测试用例的 $q$ 之和不超过 $10^5$。

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

对每个测试用例，输出 $q$ 个整数，每个整数对应相应查询的答案。

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

下图展示了第二个样例的第一组测试用例中的树。

第二个样例，第一组测试用例中的树

在第一个查询中，我们有 $x=7$，$y=5$。从 $7$ 到 $5$ 的最短路径为 $7-4-2-1-5$。

我们来计算该路径上顶点 $7$ 的“优美度”（niceness）。我们有 $g(7,7)=a_7=10=(1010)_2$，且 $g(5,7)=a_5 \ | \ a_1 \ | \ a_2 \ | \ a_4 \ | \ a_7=10 \ | \ 4 \ | \ 7 \ | \ 4 \ | \ 10=15=(1111)_2$，因此其优美度为 $2 + 4 = 6$。

接下来计算该路径上顶点 $4$ 的优美度。我们有 $g(7,4)=a_7 \ | \ a_4=10 \ | \ 4=14=(1110)_2$，且 $g(5,4)=a_5 \ | \ a_1 \ | \ a_2 \ | \ a_4=10 \ | \ 4 \ | \ 7 \ | \ 4=15=(1111)_2$，因此其优美度为 $3 + 4 = 7$。

接下来计算该路径上顶点 $2$ 的优美度。我们有 $g(7,2)=a_7 \ | \ a_4 \ | \ a_2=10 \ | \ 4 \ | \ 7=15=(1111)_2$，且 $g(5,2)=a_5 \ | \ a_1 \ | \ a_2=10 \ | \ 4 \ | \ 7=15=(1111)_2$，因此其优美度为 $4 + 4 = 8$。

接下来计算该路径上顶点 $1$ 的优美度。我们有 $g(7,1)=a_7 \ | \ a_4 \ | \ a_2 \ | \ a_1=10 \ | \ 4 \ | \ 7 \ | \ 4=15=(1111)_2$，且 $g(5,1)=a_5 \ | \ a_1=10 \ | \ 4=14=(1110)_2$，因此其优美度为 $4 + 3 = 7$。

最后，计算该路径上顶点 $5$ 的优美度。我们有 $g(7,5)=a_7 \ | \ a_4 \ | \ a_2 \ | \ a_1 \ | \ a_5=10 \ | \ 4 \ | \ 7 \ | \ 4 \ | \ 10=15=(1111)_2$，且 $g(5,5)=a_5=10=(1010)_2$，因此其优美度为 $4 + 2 = 6$。

该路径上的最大优美度出现在顶点 $2$ 处，其值为 $8$。