题意#
两个题的题意基本相同。
求连通无向图的一条路径，可以重复经过点、边，使得路径边权的异或和最大。
题解#
已知一组数，求选出若干个值使得异或和最大。
这是一个经典问题，可以从线性基中贪心构造出答案。
对于这两个题，DFS 后会将边分为树边和非树边。求出所有只有一条非树边构成的简单环，以这些小环的“边权异或和”构造线性基，贪心求答案即可。
（所有只有一条非树边构成的环的边权异或和：记录一下根到每个点的边权异或和 \(a_u\) 后，对每个非树边 \((u, v, w)\) 算一下 \(a_u \oplus a_v \oplus w\) 即可，公共祖先的那部分边权会异或成 \(0\) 的。）
BZOJ 2115 需要选一条 \(1\) ~ \(n\) 的路径边权异或和作为初始值，贪心优化答案；对于 HDU 5544，直接从 \(0\) 贪心。
证明（短）#
- 主要关心的还是走过奇数次的边，这些边的边权对答案有贡献。
- 任何一个回路，如果有非树边走了奇数次，那你可以顺着树边绕过去走一下这个非树边再原路回去；
- 非树边中走过次数的奇偶性也只有这条边改变了，被走过了偶数次；
- 而这个新加的路径的异或值就是包含这条非树边的小环的边权异或和；
- 消来消去回路上就没有非树边走过奇数次了，而又不能仅有树边走过奇数次，所以这时所有边已经都被走过偶数次了，边权异或和是 \(0\)。
- 所以对任何一个回路，总能有一组小环的边权异或和的异或，与这个回路的边权异或和相对应。
- 小环的随便组合后，从根出发绕这些小环都走一遍，就能够构造出来一个回路，使得走过的奇数次的边集，和这些小环异或出来的边集相同。
- 所以小环的边权异或和的随意组合、异或，总能构造一个回路的边权异或和，与小环的相对应。
- 综上，任何一个回路的边权异或和的集合，和若干小环随意组合的边权异或和的集合是相同的，所以问题就能规约到题解所说的做法。
证明（长）#
以下基于 HDU 5544 的题面进行证明。
下面统一称“DFS 后、只有一条非树边构成的简单环”为小环。
无向图回路的边权的异或和，可由小环组成#
对于连通的无向图，任意的一条可重复经过点、边的回路，回路的边权异或和，可以由若干小环的边权异或和，异或得到。
记这个回路为 \(D\)，起点为 \(S\)，终点为 \(T\)，经过奇数次的边集为 \(C\)。
- \(S = T\)。
- 回路 \(D\) 的边权的异或和等于 \(C\) 边权的异或和。
- 若 \(C\) 中，没有非树边，即非树边都经过了偶数次。
- 假设有树边 \(e = (u, v, w)\) 在边集 \(C\) 中。
- 树边 \(e\) 把 DFS 树划分为两个联通块 \(A\), \(B\)；
- 由于非树边最终都只经过了偶数次，按回路的顺序在点间移动，\(e\) 经过奇数次、非树边经过偶数次以后，必然起点 \(S\) 和终点 \(T\) 分别处在不同的联通块 \(A\), \(B\) 中；
- 这样有 \(S \ne T\)，矛盾。
- 因此不会有树边只经过了奇数次，\(C\) 中又没有非树边，所以 \(C\) 为空集。
- 所以所有边都只经过了偶数次，回路的边权异或和为 \(0\)。
- 假设有树边 \(e = (u, v, w)\) 在边集 \(C\) 中。
- 若 \(C\) 中，有非树边。
- 记 \(C\) 中某个非树边为 \(e = (e_u, e_v, e_w)\)；
- 记小环中，包含 \(e\) 的简单环为 \(D_e\)。
- 按以下步骤，在不引入新的经过奇数次的非树边的情况下，构造一个新回路 \(D’\) 使得 \(e\) 经过了偶数次：
- 从 \(C\) 中的起点 \(S\) 出发，只经过树边，走到点 \(e_u\) 后，按 \(D_e\) 走一遍简单环，再从点 \(e_u\) 原路返回至 \(S\)，记这个回路为 \(P\)。
- 将这个回路 \(P\) 拼到 \(D\) 的末尾，拼成路径 \(D’\)，显然 \(D’\) 依然是个回路。
- 记 \(D’\) 中经过奇数次的边集为 \(C’\)。
- 由于回路 \(P\) 中，只有 \(D_e\) 的边经过了奇数次，而 \(e\) 是 \(P\) 中唯一的非树边，所以 \(P\) 中经过奇数次的非树边只有 \(e\)。
- 所以在 \(D’\) 中 \(e\) 总共经过了偶数次，\(C’\) 中已经没有了 \(e\)。
- 在 \(P\) 中又没有其它非树边，所以 \(C’\) 中也没有引入新的非树边。
- 我们成功地从回路的经过奇数次的边中，踢掉了一个非树边。
- 对于答案，如果知道回路 \(D’\) 的边权异或和 \(ans’\)，那么 \(D\) 的边权异或和 \(ans\) 就为 \(ans’\) 异或上简单环 \(D_e\) 的边权异或和。
- 通过上述的归纳证明，任何一种回路 \(D\) 的边权异或和，都可以用若干小环的边权异或和，异或得到。
小环的任意组合，可以有回路相对应#
对于任何一种小环的组合，我们都可以构造一个指定起点 \(S\) 的回路 \(D\)，使得 \(D\) 的边权异或和，恰好等于这组小环边权异或和的异或和。
构造方法就是对每个小环，从 \(S\) 点出发，走到小环的某个点上，再绕这个小环走一圈后，原路返回到 \(S\) 点。
这样把所有小环走一遍就得到了一个从 \(S\) 出发的回路 \(D\)，并且显然 \(D\) 的边权异或和，就是这些小环各自的边权异或和的异或和。
总结#
回路、小环的任意组合，这两者都能有一个边权异或和相等的映射。
因此无向图中，求可以重复经过点、边的回路的边权异或和的最大值，等同于求小环边权异或和，任意异或能够得到的最大值。
评论