CF2236G.Criterion in Burlandia

Regions in Burlandia form a graph with $n$ vertices and $n-1$ edges, and there is exactly one path between any two vertices. Formally, the regions form a tree.

Each region has a friendliness value $a_i$.

There are $q$ queries. In each query, a pair of friends located in different regions is given. They want to know how many subsegments of the path between these regions are hospitable.

It is known that in Burlandia there are two criteria for evaluating relationships — XOR and sum. A subsegment of the path, containing some vertices lying on the path from region $x$ to region $y$, is called hospitable if it is non-empty and the sum of friendliness values on this subsegment does not exceed their XOR.

More formally, for each query you are given two vertices $x$ and $y$ $(x \neq y)$. Consider the shortest path from vertex $x$ to vertex $y$ in the tree. Let the vertices $v_1, v_2, \ldots, v_k$ form this path, where $v_1 = x$, $v_k = y$. You need to find the number of subsegments of this path for which the following condition holds: $$ 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$ — the boundaries of the subsegment of vertices on the path from $x$ to $y$.

Burlandia 的各个区域构成一个包含 $n$ 个顶点和 $n-1$ 条边的图，且任意两个顶点之间恰好存在一条路径。形式上，这些区域构成一棵树。

每个区域具有一个友好度值 $a_i$。

共有 $q$ 个查询。在每次查询中，给出一对位于不同区域的朋友。他们希望知道：连接这两个区域的路径上，有多少个子段是“宜人”的。

已知 Burlandia 中存在两种关系评估标准——异或（XOR） 和求和。若某路径子段（即路径上若干连续顶点）非空，且该子段上所有顶点的友好度之和不超过其异或值，则称该子段为“宜人”。

更形式化地，对每个查询，给定两个顶点 $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}}),$$

其中 $1 \leq l \leq r \leq k$ 表示路径上从 $x$ 到 $y$ 的顶点子段的端点。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains integers $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree, and $q$ ($1 \leq q \leq 10^5$) — the number of queries.

The second line contains an array of $n$ non-negative integers — the friendliness values of the regions ($0 \leq a_i \lt 2^{20}$).

The next $n - 1$ lines describe the edges of the tree: each line contains integers $u, v$ ($1 \leq u, v \leq n$) — an edge.

Then $q$ lines follow describing the queries. Each query is given by integers $x, y$ ($1 \leq x, y \leq n$, $x \neq y$) — the vertices that define the path for which you need to count the number of hospitable subsegments.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^5$, and that the edges indeed form a tree.

每个测试包含多个测试用例。第一行包含一个整数 $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 < 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$，且所给边确实构成一棵树。

For each query output an answer on a separate line.

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

For clarity, consider the third query from the third sample.

The path from vertex $2$ to vertex $3$ consists of vertices ${2, 4, 3}$.

The subsegment $[2; 3]$ does not satisfy the condition, since the XOR on it is $a_4 \oplus a_3 = 4 \oplus 4 = 0$, while the sum is $a_4 + a_3 = 4 + 4 = 8$.

The subsegment $[1; 3]$ does not satisfy the condition, since the XOR on it is $a_2 \oplus a_4 \oplus a_3 = 2 \oplus 4 \oplus 4 = 2$, while the sum is $a_2 + a_4 + a_3 = 2 + 4 + 4 = 10$.

It can be shown that all other 4 subsegments satisfy the condition.

For each query, output the answer in a separate line.

为清晰起见，考虑第三个样例中的第三次查询。

从顶点 $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 个子段均满足条件。

对每次查询，将答案单独输出在一行中。