题解 P4151 【[WC2011]最大XOR和路径】

· · 题解

其他题解已经将这个题的大体思路讲的很清楚了，这里补充两个证明。

设 T 是原图 G(V, E) 的任一生成树，T 的根为 1；定义一条路径 p 的权值 w(p) 为它经过的边的权值的 XOR 和，\bar p 为 p 的反向路径， t(u) 为 1 到 u 树上路径，\bar t(u) 为 u 到 1 的树上路径，f(u) 为 t(u) 权值。

定理1：从点 1 出发回到 1 的所有路径的权值构成的集合 A 等于 D: \{\bigoplus [ f(u) \oplus w(u,v) \oplus f(v)] \mid (u, v) \in E \setminus T\}.

证：

- $(u_i, u_{i + 1}) \in E(1 \leq i \leq k - 1)
  • u_1 = u_k = 1
\begin{aligned} &\therefore w(u_1, u_2, \dots, u_k) \\ &= \bigoplus_{i = 1}^{n - 1}w(u_i, u_{i + 1}) \\ &= \bigoplus_{i = 1}^{n - 1}w(u_i, u_{i + 1}) \oplus f(u_1) \oplus f(u_2) \oplus f(u_2) \oplus \dots \oplus f(u_{k - 1}) \oplus f(u_{k - 1}) \oplus f(u_k) \\ &= \bigoplus_{i = 1}^{n - 1}[f(u_i) \oplus w(u_i, u_{i + 1}) \oplus f(u_{i + 1})] \end{aligned}

若 (u_i, u_{i + 1}) \in T(1 \leq i \leq k - 1)，不妨设 u_i 是 u_{i + 1} 的父亲，则 f(u_i) \oplus w(u_i, u_{i + 1}) \oplus f(u_{i + 1}) = f(u_{i + 1}) \oplus f(u_{i + 1}) = 0，因此 w(u_1, u_2, \dots, u_k) = \bigoplus[1 \leq i < n, (u_i, u_i + 1) \in E \setminus T][f(u_i) \oplus w(u_i, u_{i + 1}) \oplus f(u_{i + 1})] \in D.

\forall s = \bigoplus_{i = 1}^k f(u_i) \oplus w(u_i, v_i) \oplus f(v_i) \in D$，有 $s = w[t(u_1), \bar t(v_1), t(u_2), \bar t(v_2), \dots, t(u_k), \bar t(v_k)] \in A

定理2：记从点 1 出发回到 1 的所有路径的权值构成的集合为 A，则从点 1 出发到点 N 的所有路径的权值集合 B 等于 \{f(N) \oplus w \mid w \in A\}.

证：

记原式右边为 C，

\begin{aligned} &w(p) \in A \\ &\implies w(p) \oplus f(N) = w[p, t(N)] \in B \\ &\implies C \subseteq B \end{aligned} \begin{aligned} &\forall w(p) \in B, w(p) \oplus f(N) = w[p, \bar t(N)] \in A \\ &\implies w(p) \in C \\ &\implies B \subseteq C \\ &\implies B = C \end{aligned}

注意到 \max B = \max\{f(N) \oplus w \mid w \in D\} 即为所求，对 D 构造线性基即可。

代码与其他题解类似，这里略去。

我注意到许多题解的解释是对“环的权值构造线性基”，但代码里却“隐式地”使用了上述两个定理，这在逻辑上有所跳跃。同时，由上述分析可以看出，本题取任何一个生成树均可，无需强调“dfs 树”或“bfs 树”等。