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

Input

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

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

Examples

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

output

2 4 3 
6 6 6 6 
2 

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

output

8 6 7 7 
6 6 4 7 
6 4 

input 

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

output

7 7 5 7 

Note

The image below shows the 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$.

解题思路

  一开始想着按位来考虑，结果发现这样并不好做。实际上题解给出的做法挺暴力的，但不好想到。

  注意到 $a_i$ 最大为 $10^9$，意味着在二进制下 $a_i$ 最多有 $30$ 位。那么从 $x$ 到 $y$ 的路径中最多只需考虑 $2 \times 30$ 个节点作为中间节点 $z$。这是因为最多有 $30$ 个节点使得 $g(x,z)$ 为 $1$ 的位多 $1$，即那些从 $x$ 到 $y$ 的路径中某一位第一次出现 $1$ 的节点（离 $x$ 最近），而其他的节点完全可以由这 $30$ 个节点来表示（因为不改变 $g(x,z)$ 的结果）。同理分析 $g(y,z)$。当找到这些节点后，直接暴力枚举当作 $z$，计算 $g(x,z) + g(y,z)$ 取最大值即可。

  问题是如何找到这些节点，以及如何快速计算 $g(x,z)$。由于是关于树上的路径问题，因此参考求 $\text{lca}$ 用到的倍增思想。

  定义 $f(u,i)$ 表示从 $u$ 到树根的路径上距离 $u$ 最近的且权值的第 $i$ 位是 $1$ 的节点。分情况讨论，如果 $a_u$ 的第 $i$ 位是 $1$，那么很明显有 $f(u,i) = u$；否则考虑 $u$ 的父节点 $p_u$，那么有 $f(u,i) = f(p_u,i)$。$f(u,i)$ 可以借助 bfs 以 $O(n \log{A})$ 的时间复杂度预处理出来。

  定义 $h(u,i)$ 表示从 $u$ 到往上跳 $2^i$ 步的路径中所有节点权值的按位或结果（不包括节点 $u$ 的权值）。首先考虑从 $u$ 到往上跳 $2^i$ 步的路径上的中间节点，即从 $u$ 到往上跳 $2^{i-1}$ 步后的节点 $\text{fa}(u,i-1)$，这一半路径的按位或结果就是 $h(u,i-1)$，另外一半路径的按位或结果就是 $h(\text{fa}(u,i-1),i-1)$，因此有 $h(u,i) = h(u,i-1) \mid h(\text{fa}(u,i-1),i-1)$。$h(u,i)$ 可以借助 bfs 以 $O(n \log{n})$ 的时间复杂度预处理出来。

  假设 $p = \text{lca}(x,z)$，那么要计算 $g(x,z)$，只需借助 $h$ 数组分别求从 $x$ 到 $p$ 以及从 $z$ 到 $p$ 路径上的权值按位或，具体做法与求最近公共祖先 $p$ 类似。

  有一个疑问的地方就是，由于 $g(u,i)$ 得到的是从 $u$ 到树根这条路径上距离 $u$ 最近的节点，如果在 $x$ 到 $y$ 的路径上距离 $x$ 最近的那个节点在 $p$ 到 $y$ 的路径上（$p = \text{lca}(x,y)$），那很明显通过 $f$ 数组是得不到的，如下图权值为 $1$ 的红色节点：

  实际上对于这些距离 $x$ 最近但在 $p$ 到 $y$ 的路径上的节点，假设为 $z'$，如果 $z'$ 也是距离 $y$ 最近的节点那么会被选择作为 $z$。如果不是距离 $y$ 最近的节点，意味着 $a_{z'}$ 中为 $1$ 的位，都存在与之对应的离 $y$ 更近的节点，假设这些节点中距离 $z'$ 最近的是 $z''$，很明显有 $g(y,z') = g(y,z'')$，$g(x,z'') + g(y,z'') \geq g(x,z') + g(y,z')$，因此 $z'$ 不会选作为 $z$。同理分析 $y$。因此只需考虑从该节点到树根路径上的距离最近的节点即可，当然要满足节点在 $x$ 到 $y$ 的路径上，即节点的深度不能小于 $p$ 的深度。

  AC 代码如下，时间复杂度为 $O(q \cdot \log{A} \cdot \log{n})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 10, M = N * 2;

int w[N];
int head[N], e[M], ne[M], idx;
int fa[N][18], dep[N], s[N][18], g[N][30];
int q[N];

void add(int u, int v) {
    e[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 17; i >= 0; i--) {
        if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    }
    if (a == b) return a;
    for (int i = 17; i >= 0; i--) {
        if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    }
    return fa[a][0];
}

int query(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int ret = w[a] | w[b];
    for (int i = 17; i >= 0; i--) {
        if (dep[fa[a][i]] >= dep[b]) {
            ret |= s[a][i];
            a = fa[a][i];
        }
    }
    if (a == b) return __builtin_popcount(ret);
    for (int i = 17; i >= 0; i--) {
        if (fa[a][i] != fa[b][i]) {
            ret |= s[a][i] | s[b][i];
            a = fa[a][i], b = fa[b][i];
        }
    }
    ret |= s[a][0] | s[b][0];
    return __builtin_popcount(ret);
}

void solve() {
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    memset(head, -1, n + 10 << 2);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    memset(dep, 0x3f, n + 10 << 2);
    dep[0] = 0, dep[1] = 1;
    int hh = 0, tt = -1;
    q[++tt] = 1;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i != -1; i = ne[i]) {
            if (dep[e[i]] > dep[u] + 1) {
                dep[e[i]] = dep[u] + 1;
                q[++tt] = e[i];
                fa[e[i]][0] = u;
                s[e[i]][0] = w[u];
                for (int j = 1; j <= 17; j++) {
                    fa[e[i]][j] = fa[fa[e[i]][j - 1]][j - 1];
                    s[e[i]][j] = s[e[i]][j - 1] | s[fa[e[i]][j - 1]][j - 1];
                }
            }
        }
        for (int i = 0; i <= 29; i++) {
            g[u][i] = g[fa[u][0]][i];
            if (w[u] >> i & 1) g[u][i] = u;
        }
    }
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int p = lca(a, b), ret = 0;
        for (int i = 0; i <= 29; i++) {
            if (dep[g[a][i]] >= dep[p]) ret = max(ret, query(a, g[a][i]) + query(b, g[a][i]));
            if (dep[g[b][i]] >= dep[p]) ret = max(ret, query(a, g[b][i]) + query(b, g[b][i]));
        }
        printf("%d ", ret);
    }
    printf("\n");
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

参考资料

  Codeforces round #900 (Div.3) Editorial：https://codeforces.com/blog/entry/120813

  Codeforces Round 900 (Div. 3) G：https://zhuanlan.zhihu.com/p/658961812