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$$$,并且边确实形成一棵树。
输出
对于每个查询,在单独的行上输出一个答案。
示例
输入复制
34 30 0 4 11 21 31 41 42 32 44 30 4 1 21 31 42 41 22 32 44 33 2 4 41 22 43 41 21 32 3
输出复制
3666103254
注意
为了清楚起见,请考虑第三个示例中的第三个查询。
从顶点 $$$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个子段都满足条件。
对于每个查询,在单独的行中输出答案。