CF1983G.Your Loss

给定一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$，以及一个长度为 $n$ 的数组。第 $i$ 个节点的权值为 $a_i$。有 $q$ 个询问，每个询问给定两个节点 $x$ 和 $y$。

考虑从编号为 $x$ 的节点到编号为 $y$ 的节点的路径。设该路径为 $x = p_0, p_1, p_2, \ldots, p_r = y$，其中 $p_i$ 表示路径上的中间节点。请计算 $\sum_{i=0}^{r} a_{p_i} \oplus i$ 的值，其中 $\oplus$ 表示 异或 运算。

更正式地说，计算

$$\sum_{i =0}^{r} a_{p_i}\oplus i$$

。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每组测试数据包含以下内容。

每组数据的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示节点数。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。保证 $u \ne v$，且所有边构成一棵树。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 5 \cdot 10^5$），表示每个节点的权值。

接下来一行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问的数量。

接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示路径的起点和终点。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$，所有测试用例中 $q$ 的总和不超过 $10^5$。

对于每个询问，输出一个整数，表示题目要求的路径和。

由 ChatGPT 4.1 翻译