G. Your Loss 详细题解

题目重述

给定一棵 $n$ 个节点的树，节点 $i$ 有权值 $a_i$。有 $q$ 个查询，每个查询给出两个节点 $x$ 和 $y$。设从 $x$ 到 $y$ 的路径上的节点按顺序为 $p_0 = x, p_1, \dots, p_r = y$，要求计算

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

其中 $\oplus$ 表示按位异或。输出每个查询的结果。

数据范围

• $t$ 个测试用例，$1 \le t \le 10^4$。
• 单个测试用例中 $1 \le n \le 5\cdot 10^5$，所有测试用例的 $n$ 之和 $\le 5\cdot 10^5$。
• $1 \le a_i \le 5\cdot 10^5$，因此 $a_i < 2^{20}$。
• $1 \le q \le 10^5$，所有测试用例的 $q$ 之和 $\le 10^5$。
• 时间和内存限制：3 秒，256 MB。

核心思路

直接按路径遍历每个节点会超时（$O(q \cdot n)$）。需要将路径拆分为若干连续段，并快速计算每段内形如 $\sum (a \oplus (\text{offset} + i))$ 的和。由于树结构，可以采用树链剖分将任意路径分解为 $O(\log n)$ 条重链上的连续区间。对于每个区间，我们需要高效计算该区间内所有节点值与一个等差数列 $(\text{base} + i)$ 进行异或的和。

二进制拆位

因为异或运算按位独立，我们可以逐位计算贡献：

$$\sum_{j=1}^{L} (x_j \oplus y_j) = \sum_{b=0}^{B-1} 2^b \cdot \big( \#\{j \mid (x_j)_b \neq (y_j)_b\} \big) $$

其中 $B = \lceil \log_2(\max a_i + \text{路径长度})\rceil \le 20$（因为 $a_i \le 5\cdot 10^5 < 2^{20}$，$i \le n \le 5\cdot 10^5 < 2^{19}$，所以 $20$ 位足够）。

对于一段长度为 $L$ 的区间，节点值序列为 $val_0, val_1, \dots, val_{L-1}$，对应下标 $i$ 从 $0$ 到 $L-1$（全局路径中的实际下标为 $\text{base}+i$）。对于第 $b$ 位，设：

• $cnt_1$ 为区间内节点值的第 $b$ 位为 $1$ 的个数；
• $ones$ 为区间内 $\text{base}+i$ 的第 $b$ 位为 $1$ 的个数（即整数 $\text{base}, \text{base}+1, \dots, \text{base}+L-1$ 中第 $b$ 位为 $1$ 的个数）。

则第 $b$ 位不同的个数为：

$$cnt_1 \cdot (L - ones) + (L - cnt_1) \cdot ones = cnt_1 \cdot L + (L - 2cnt_1) \cdot ones $$

因此该位对总和的贡献为 $2^b$ 乘以该值。

快速计算 $cnt_1$ 和 $ones$

• $cnt_1$：对于树链剖分后的每条重链，我们可以预处理该链上所有节点值的二进制前缀和。即对于链上的节点序列 $seq[0..len-1]$，预计算 pre[bit][i] 表示前 $i$ 个节点中第 $bit$ 位为 $1$ 的个数。这样任意区间 $[l, r]$ 内的 $cnt_1$ 可在 $O(1)$ 内得到：pre[bit][r+1] - pre[bit][l]。
• $ones$：需要计算等差数列 $base, base+1, \dots, base+L-1$ 中第 $b$ 位为 $1$ 的个数。这是一个数学问题，可以用公式快速求出。设 $T = 2^{b+1}$，则一个非负整数 $x$ 的第 $b$ 位为 $1$ 当且仅当 $x \bmod T \in [2^b, 2^{b+1}-1]$。因此区间 $[L, R]$ 内第 $b$ 位为 $1$ 的个数为：$$f(R) - f(L-1)$$ 其中 $f(x) = \left\lfloor\frac{x+1}{T}\right\rfloor \cdot \frac{T}{2} + \max(0, (x+1)\bmod T - \frac{T}{2})$。 该计算为 $O(1)$。

处理路径方向

树链剖分将路径分解为若干段：

• 从 $x$ 向上到 LCA（不含 LCA）的若干重链段，这些段在重链上的顺序是从深到浅，但节点值的顺序与重链存储方向相反。由于我们只关心 $cnt_1$（与顺序无关），可以直接使用正向区间统计节点值。但注意，此时区间对应全局下标 $i$ 是递增的，而我们统计 $cnt_1$ 时不受顺序影响，所以 $cnt_1$ 直接取正向区间内节点即可。
• 从 LCA 向下到 $y$ 的若干重链段，这些段在重链上是从浅到深，与存储方向一致，直接取正向区间。

我们需要记录整个路径上每个节点对应的全局下标 $i$（从 $0$ 开始）。对于向上段，由于路径是逆向的，但计算贡献时 $i$ 仍然是顺序递增的，因此我们可以先计算当前段长度 $len$，那么该段的起始下标为当前全局下标 $cur$，节点顺序是逆向的。因为异或运算对顺序不敏感（只是每个节点与不同 $i$ 异或），我们的统计方式已经通过 $cnt_1$ 和 $ones$ 分离了节点值和下标的影响，所以可以直接用正向区间节点值（$cnt_1$）和连续下标区间 $[cur, cur+len-1]$ 计算，而不需要真正反转节点序列。

算法流程

1. 预处理：
   • 对树进行轻重链剖分，得到每个节点的父节点、深度、子树大小、重儿子、链顶、在重链中的位置。
   • 记录每条重链的节点列表（从链顶到链底）。
   • 对于每条重链，对所有 $b = 0 \dots 19$，计算前缀和 pre[bit][i]（$i$ 从 $0$ 到 $len$）。
2. 处理查询：
   • 输入 $x, y$。
   • 求出 $l = \text{LCA}(x, y)$。
   • 初始化当前全局下标 cur = 0，答案 ans = 0。
   • 处理向上段（$x$ 到 $l$，包括 $l$）：
     • 将路径从 $x$ 向上跳重链，直到到达 $l$ 所在链。
     • 对每一段（链顶到当前节点），设该段在链上的区间为 $[lpos, rpos]$（$lpos$ 为链顶位置，$rpos$ 为当前节点位置），长度为 $len = rpos - lpos + 1$。
     • 调用函数 calc(chain_id, lpos, rpos, cur)，该函数：
       • 对于每个 $b$，计算 $cnt_1$（利用前缀和），$ones$（利用数学公式），得到该位贡献。
       • 将贡献累加到 ans。
     • 更新 cur += len，然后 $x = par[top[x]]$ 继续循环。
   • 处理向下段（$l$ 到 $y$，不包括 $l$）：
     • 从 $y$ 向上收集所有需要经过的重链段，但顺序是反向的（因为从 $l$ 向下到 $y$ 才是正向顺序）。
     • 先将所有段（从 $y$ 到 $l$ 的路径）收集到一个数组 segs 中，每段存储 (chain_id, lpos, rpos)，其中 $lpos$ 是段内较浅的一端（靠近 $l$），$rpos$ 是较深的一端（靠近 $y$）。收集时注意 $l$ 本身不包含在内，所以最后一段从 $pos[l]+1$ 开始。
     • 将 segs 反转，使得顺序变为从 $l$ 向下到 $y$。
     • 遍历 segs，对每个段调用 calc，每次更新 cur。
   • 输出 ans。

复杂度

• 预处理：$O(n \cdot B)$，其中 $B=20$。
• 每个查询：路径分解为 $O(\log n)$ 段，每段计算 $B$ 位，每位的计算为 $O(1)$，因此单次查询 $O(B \log n)$。对于 $q \le 10^5$，总复杂度 $O((n+q)B \log n)$，在给定范围内可接受。

正确性说明

• 树链剖分保证任意路径可以被 $O(\log n)$ 条重链上的连续区间覆盖。
• 因为异或运算按位独立，并且我们正确统计了每一位上节点值与下标不同的个数，因此累加后得到准确的总和。
• 公式计算 $ones$ 时使用了闭区间上的计数，精确无误。
• 向上段虽然节点顺序与链存储顺序相反，但 $cnt_1$ 只依赖于节点集合（与顺序无关），而 $ones$ 依赖于顺序递增的下标，所以直接使用正向区间计算是正确的（因为正向区间对应的节点集合与逆向集合相同，只是排列不同，但下标 $i$ 的等差数列仍按全局顺序递增，不影响统计结果）。

实现细节

• 由于 $a_i \le 5\times 10^5 < 2^{20}$，且路径长度最多 $5\times 10^5 < 2^{19}$，所以 $B = 20$ 足够。
• 为了节省内存，可以只存储每条重链的 $20$ 个前缀和数组，每条链的长度总和为 $n$，总空间 $O(n \cdot B)$，约 $5\times 10^5 \times 20 = 10^7$ 个整数，内存约 $40$ MB，在限制内。
• 数学公式中需要用到 $64$ 位整数（因为 $base+L-1$ 可能达到 $10^6$ 级别，但仍在 $2^{31}$ 内），使用 long long 即可。

总结

本题是树上路径异或求和问题，利用树链剖分转化为区间问题，再利用二进制拆位和数学公式快速计算每个区间内节点与等差数列的异或和。通过预处理每条重链上各二进制位的前缀和，可以在 $O(\log n \cdot \log \max a)$ 时间内回答每个查询，满足大数据范围的要求。