← 返回题目列表

Codeforces · 1778/E

E. 树倒了!

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

最近,一棵树从天而降砸在了鲍勃的头上。该树有 $$$n$$$ 个节点。树的每个节点 $$$u$$$ 上都写有一个整数 $$$a_u$$$。但这棵树没有固定的根,因为它是从天上掉下来的。

Bob 目前正在研究这棵树。为了增加一些变化,爱丽丝提出了一个游戏。首先,Bob 选择某个节点 $$$r$$$ 作为树的根。之后,Alice 选择一个节点 $$$v$$$ 并告诉他。然后 Bob 可以从 $$$v$$$ 的子树中选取一个或多个节点。他的分数将是他所选择的节点上写入的所有值的按位异或。鲍勃必须找到给定 $$$r$$$ 和 $$$v$$$ 下他可以获得的最高分。

由于鲍勃不是一个善于解决问题的人,他要求你帮助他找到答案。你能帮助他吗?您需要为同一棵树找到 $$$r$$$ 和 $$$v$$$ 的多种组合的答案。

回想一下,树是一个没有循环的连通无向图。节点 $$$u$$$ 的子树是所有节点 $$$y$$$ 的集合,使得从 $$$y$$$ 到根的简单路径经过 $$$u$$$。请注意,$$$u$$$ 位于$$$u$$$ 的子树中。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2 \cdot 10^5$$$) — 树的节点数。

下一行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) - 写入节点上的值。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u, v\leq n$$$; $$$u\neq v$$$),表示节点 $$$u$$$ 和节点 $$$v$$$ 之间有一条无向边。保证给定的边形成一棵树。

下一行包含一个整数 $$$q$$$ ($$$1\leq q\leq 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含两个整数 $$$r$$$ 和 $$$v$$$ ($$$1\leq r, v\leq n$$$) - Bob 定义的根节点和 Alice 选择的节点。

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

输出

对于每个测试用例,在每个查询中打印一行,其中包含一个整数,表示 Bob 可以获得的最大分数。

示例

输入 #1

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

输出 #1

15
6
29
11
3
8
11
15
3

注意

在下面的每张图中,绿色节点是 Bob 选择的节点,红色节点是 Alice 选择的节点。节点的值放置在节点旁边的蓝色框中。

考虑第一个例子。在第一个查询中,如果我们将根节点 $$$4$$$ 放在树的顶部,则树如下图所示:

第一个查询中根节点为 $$$4$$$ 的树。

在第二个查询中,如果根节点 $$$3$$$ 位于树的顶部,则树如下图所示:

第二个查询中根节点为 $$$3$$$ 的树。

在第三个查询中,如果根节点 $$$1$$$ 位于树的顶部,则树如下所示:

第三个查询中根节点为 $$$1$$$ 的树。