← 返回题目列表

Codeforces · 1878/G

G. wxhtzdy ORO 树

中文机器翻译题面 查看原题

在(终于)获得 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$$$。