CF1882D Tree XOR 题解

题目大意

给定一棵 \(n\) 个点的树，点 \(i\) 上有权值 \(a_i\)（\(0 \le a_i < 2^{20}\)）。以 \(r\) 为根时，一次操作为：任选顶点 \(v\) 与非负整数 \(c\)，把 \(v\) 的子树（相对根 \(r\) 而言）中所有点的权值异或上 \(c\)，代价为 \(s_v \cdot c\)，其中 \(s_v\) 是该子树的顶点数。要求通过若干次操作使所有点权值相等，最小总代价记为 \(m_r\)。对每个 \(r\) 输出 \(m_1, m_2, \dots, m_n\)。

固定根时

先把根 \(r\) 固定，分析合法操作序列的结构。

引理（合并不亏）：每个顶点至多施法一次

设对同一顶点 \(v\) 施法了 \(k\) 次，参数为 \(c_1, \dots, c_k\)。由于异或可交换、可结合，这 \(k\) 次施法的总效果等同于施法一次 \(c = c_1 \oplus c_2 \oplus \cdots \oplus c_k\)。

代价，异或是"无进位加法"，故 \(x \oplus y \le x + y\)，归纳可得

\(s_v \cdot (c_1 \oplus c_2 \oplus \cdots \oplus c_k) \le s_v \cdot (c_1 + c_2 + \cdots + c_k)\)

即合并成一次操作代价不增。因此下文假设每个顶点 \(v\) 只施法一次，设其异或量为 \(x_v \ge 0\)（\(x_v = 0\) 表示不施法）。

引理（强制性）：非根顶点的施法量被唯一确定

设最终所有点的共同值为 \(T\)。记 \(P(v)\) 为根到 \(v\) 的路径上所有顶点（含端点）的 \(x\) 值之异或。由于恰好是这些祖先（含自身）的施法影响了 \(v\)，点 \(v\) 的最终值为

\(a_v \oplus P(v) = T \quad (\forall v)\)

任取非根点 \(v\)，设其父为 \(p\)。把 \(v\) 与 \(p\) 的等式相异或，注意 \(P(v) = P(p) \oplus x_v\)，得

\(a_v \oplus a_p \oplus x_v = 0 \quad \Longrightarrow \quad x_v = a_v \oplus a_p\)

\(T\) 被消去了说明每个非根点的施法量与目标值无关，是被强制确定的。

\(m_r\) 的闭式

总代价为

\(\sum_{v \ne r} s_v \cdot (a_v \oplus a_{par(v)}) + n \cdot x_r\)

其中第二项只有 \(x_r\) 是自由的，取 \(x_r = 0\) 最优。于是

\(m_r = \sum_{v \ne r} s_v \cdot (a_v \oplus a_{par(v)})\)

且最优方案下所有点最终都等于 \(a_r\)（根处根本不用施法）。

换根 DP

上式若对每个根分别计算是 \(O(n^2)\)。把求和改写成边的视角：

\(m_r = \sum_{e=(u,w)} (a_u \oplus a_w) \cdot \big|\text{删去 } e \text{ 后不包含 } r \text{ 的连通块}\big|\)

根从 \(u\) 移到相邻点 \(v\) 时，考虑任意边 \(e' \ne (u,v)\)——\(u\) 与 \(v\) 在 \(T - e'\) 中位于同一连通块（\(u\) 到 \(v\) 的路径不经过 \(e'\)），所以 \(e'\) 的"不含根的一侧"不变，贡献不变。唯一变化的只有边 \((u,v)\) 自己：

• 以 \(u\) 为根：贡献为 \(s_v \cdot d\)，其中 \(d = a_u \oplus a_v\)，\(s_v\) 是以 \(u\) 为根时 \(v\) 的子树大小
• 以 \(v\) 为根：不含 \(v\) 的一侧大小为 \(n - s_v\)，贡献为 \((n - s_v)\cdot d\)

于是得到转移

\(m_v = m_u + (n - 2\,s_v)\cdot (a_u \oplus a_v)\)