← 返回题目列表

Codeforces · 2236/G

G. Burlandia 中的标准

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

Burlandia 中的区域形成一个具有 $$$n$$$ 个顶点和 $$$n-1$$$ 个边的图,并且任意两个顶点之间只有一条路径。形式上,这些区域形成一棵树。

每个地区都有一个友好度值$$$a_i$$$。

有 $$$q$$$ 查询。在每个查询中,给出一对位于不同地区的朋友。他们想知道这些区域之间的路径有多少个子段 热情好客.

众所周知,在 Burlandia 中有两个评估关系的标准 - XOR 和 sum。路径的子段,包含位于从区域 $$$x$$$ 到区域 $$$y$$$ 的路径上的一些顶点,称为 热情好客 if 它非空 并且该子分段上的友好度值的总和不超过它们的异或。

更正式地说,对于每个查询,您都会获得两个顶点 $$$x$$$ 和 $$$y$$$ $$$(x \neq y)$$$。考虑树中从顶点 $$$x$$$ 到顶点 $$$y$$$ 的最短路径。让顶点$$$v_1, v_2, \ldots, v_k$$$ 形成这条路径,其中$$$v_1 = x$$$, $$$v_k = y$$$。您需要找到满足以下条件的该路径的子段数: $$a_{v_{l}} \oplus a_{v_{l+1}} \oplus \ldots \oplus a_{v_{r}} \geq (a_{v_{l}} + a_{v_{l+1}} + \ldots + a_{v_{r}}),$$ where $$$1 \leq l \leq r \leq k$$$ — 从 $$$x$$$ 到 $$$y$$$ 的路径上顶点子段的边界。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 树中的顶点数,以及 $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — 查询数。

第二行包含一个 $$$n$$$ 非负整数数组 — 区域的友好度值 ($$$0 \leq a_i \lt 2^{20}$$$)。

接下来的 $$$n - 1$$$ 行描述树的边:每行包含整数 $$$u, v$$$ ($$$1 \leq u, v \leq n$$$) — 一条边。

然后 $$$q$$$ 行描述查询。每个查询由整数 $$$x, y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$) 给出 - 这些顶点定义了需要计算其好客子段数量的路径。

保证所有测试用例的 $$$n$$$ 之和和 $$$q$$$ 之和不超过 $$$10^5$$$,并且边确实形成一棵树。

输出

对于每个查询,在单独的行上输出一个答案。

示例

输入
复制

3
4 3
0 0 4 1
1 2
1 3
1 4
1 4
2 3
2 4
4 3
0 4 1 2
1 3
1 4
2 4
1 2
2 3
2 4
4 3
3 2 4 4
1 2
2 4
3 4
1 2
1 3
2 3

输出
复制

3
6
6
6
10
3
2
5
4

注意

为了清楚起见,请考虑第三个示例中的第三个查询。

从顶点 $$$2$$$ 到顶点 $$$3$$$ 的路径由顶点 $$${2, 4, 3}$$$ 组成。

子段$$$[2; 3]$$$ 不满足条件,因为其异或为 $$$a_4 \oplus a_3 = 4 \oplus 4 = 0$$$,而总和为 $$$a_4 + a_3 = 4 + 4 = 8$$$。

子段$$$[1; 3]$$$ 不满足条件,因为其异或为 $$$a_2 \oplus a_4 \oplus a_3 = 2 \oplus 4 \oplus 4 = 2$$$,而总和为 $$$a_2 + a_4 + a_3 = 2 + 4 + 4 = 10$$$。

可以证明,所有其他4个子段都满足条件。

对于每个查询,在单独的行中输出答案。