题解：CF1983G Your Loss

· · 题解

核心思路

按位拆分

题目要求计算 \sum (a_i \oplus \text{dist})。由于异或运算在每一位上是独立的，我们可以枚举二进制的每一位 k (0 \le k < 20) 分别计算。

对于第 k 位，我们需要统计路径上满足以下条件的节点 v 的数量：

b_k(a_v) \neq b_k(\text{dist}(x, v))

令 b_k(val) 表示数值 val 的第 k 位（0 或 1）。上述不等式等价于异或值为 1。根据容斥原理，满足条件的次数为：

\text{Count} = \sum_{v \in Path} b_k(a_v) + \sum_{v \in Path} b_k(\text{dist}) - 2 \cdot \sum_{v \in Path} (b_k(a_v) \land b_k(\text{dist}))

我们只需要分别维护这三项，最后乘上 2^k 累加到答案即可。

三项的计算方法

对于固定的位 k，模数 M = 2^{k+1}。

  1. Term 1: \sum b_k(a_v)

    • 这是基础的树上路径点权和。

    • 预处理根到每个点的前缀和 pre\_a，通过 pre\_a_x + pre\_a_y - 2 \cdot pre\_a_{LCA} + \dots O(1) 计算。

  2. Term 2: \sum b_k(\text{dist})

    • 这是一个纯数学问题，与节点权值 a_v 无关。

    • 条件 b_k(\text{dist}) = 1 等价于 \text{dist} \pmod M \in [2^k, M-1]。

    • 由于 \text{dist} = C \pm dep_v，这转化为 dep_v \pmod M 落在某个特定区间。

    • 我们只需要计算深度区间 [D_{min}, D_{max}] 内有多少个数模 M 落在目标区间内。这可以 O(1) 计算

  3. Term 3: \sum (b_k(a_v) \land b_k(\text{dist}))

    • 这是难点。我们需要统计路径上满足 b_k(a_v) = 1 且 dep_v \pmod M 在特定区间 [L, R] 内的节点数。

    • 离线 + DFS + BIT：

      • 我们将询问挂载在节点上，利用 DFS 序和差分思想。

      • 在 DFS 过程中，维护一个大小为 M 的树状数组 (BIT)。BIT 的下标是 dep_u \pmod M。

      • 进入节点 u：如果 b_k(a_u) = 1，在 BIT_{dep_u \pmod M} 处加 1。

      • 处理询问：在节点 u 处查询 BIT 的区间和 query(L, R)。利用差分：Ans(Path) = Query(x) - Query(fa_{LCA}) \dots。

      • 离开节点 u：回溯，在 BIT_{dep_u \pmod M} 处减 1。

复杂度分析