CF2236G Criterion in Burlandia

Burlandia 的各个区域形成了一个包含 $n$ 个顶点和 $n-1$ 条边的图，且任意两个顶点之间恰好有一条简单路径。形式上，这些区域形成了一棵树。 每个区域有一个友好度值 $a_i$。 有 $q$ 个查询，每个查询会给出两个分别位于不同区域的朋友。他们想知道，从这两个区域之间路径的所有连续子段中，有多少个“宜人”的子段。 在 Burlandia，衡量关系有两种标准——XOR（异或）与和。若路径上的某个连续子段，包含从区域 $x$ 到区域 $y$ 路径上的若干顶点，且该子段的友好度之和不超过异或值，则称该子段是“宜人”的。 更具体地说，每个询问会给出两个顶点 $x$ 和 $y$（$x \neq y$）。设从顶点 $x$ 到顶点 $y$ 的最短路径经过 $v_1, v_2, \ldots, v_k$，其中 $v_1 = x$，$v_k = y$。你需要计算有多少个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq k$，使得： $$ a_{v_l} \oplus a_{v_{l+1}} \oplus \dots \oplus a_{v_r} \geq a_{v_l} + a_{v_{l+1}} + \dots + a_{v_r} $$ 即该路径上从 $v_l$ 到 $v_r$ 形成的连续子段是“宜人”的。

每组测试包含多组测试数据。第一行是一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。接下来是每组测试的描述。 每组测试数据的第一行为两个整数 $n$（$2 \leq n \leq 10^5$）表示树的顶点数，$q$（$1 \leq q \leq 10^5$）表示询问数。 第二行为 $n$ 个非负整数组成的数组，表示各区域的友好度 $a_i$（$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$ 的总和不超过 $10^5$，$q$ 的总和不超过 $10^5$，输入的边保证构成一棵树。

对于每个查询，输出一行，一个整数表示“宜人”子段的数量。

为方便理解，请参考第三组样例的第三个询问。 从顶点 $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 个子段均满足条件。 对于每个查询，输出一行答案。 由 ChatGPT 5 翻译