在(终于)获得 IOI 2023 的资格后,wxhtzdy 非常高兴,所以他决定做大多数有竞争力的程序员所做的事情:尝试猜测 IOI 上将出现的问题。在这个过程中,他不小心出了一道题,他觉得这题真的很酷。
给你一棵树(一个连通的非循环图),它有 $$$n$$$ 个顶点和 $$$n-1$$$ 个边。顶点 $$$i$$$ ($$$1 \le i \le n$$$) 的值为 $$$a_i$$$。
让我们将 $$$g(u, v)$$$ 定义为从 $$$u$$$ 到 $$$v$$$ 的最短路径上所有顶点的值的按位或。例如,假设我们要从示例中的第一个测试用例计算树上的 $$$g(3, 4)$$$。从 $$$3$$$ 到 $$$4$$$ 的路径上有顶点 $$$3$$$、$$$1$$$、$$$4$$$。然后,$$$g(3, 4) = a_3 \ | \a_1\| \ a_4$$$(这里$$$|$$$表示按位或运算)。
此外,您还会收到 $$$q$$$ 查询,每个查询如下所示:
给你 $$$x$$$ 和 $$$y$$$。让我们考虑所有顶点 $$$z$$$,使得 $$$z$$$ 位于从 $$$x$$$ 到 $$$y$$$ (包含)的最短路径上。
让我们将顶点 $$$z$$$ 的好度定义为 $$$g(x, z)$$$ 中的非零位数和 $$$g(y, z)$$$ 中的非零位数之和。您需要找到从$$$x$$$ 到$$$y$$$ 的最短路径上所有顶点$$$z$$$ 中的最大niceness。
由于在解决 SIO 上的仅输出问题后他的大脑真的很累(他必须这样做才能获得 IOI 资格),因此他需要你帮助解决这个问题。
输入
输入的第一行包含一个整数 $$$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$$$ 行包含 2 个整数 $$$x, y$$$ ($$$1 \le x, y \le n$$$) — 每个查询的顶点 $$$x$$$ 和 $$$y$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例输出 $$$q$$$ 个整数,每个整数都是相应查询的答案。
示例
输入 #1
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
输出 #1
2 4 3 6 6 6 6 2
输入 #2
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
输出 #2
8 6 7 7 6 6 4 7 6 4
输入 #3
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
输出 #3
7 7 5 7
注意
下图显示了第二个示例(第一个测试用例)中的树。
第二个示例的树,第一个测试用例
在第一个查询中,我们有 $$$x=7$$$,$$$y=5$$$。从 $$$7$$$ 到 $$$5$$$ 的最短路径是 $$$7-4-2-1-5$$$。
让我们计算一下这条路径上顶点 $$$7$$$ 的好度。我们有 $$$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$$$。