Codeforces 1680F - Lenient Vertex Cover 题解
题意
给定一张无向简单连通图，要求给每个点标记 0/1。
记标记为 1 的点为选中的点。要求：
- 每条边至少有一个端点被选中；
- 最多只有一条边的两个端点都被选中。
做法
首先如果我们删掉那个关键边，剩下所有被选中的点之间不能有连边，这个就很像二分图。同时可以发现没有被选的点之间也不能有连边。所以就等价于从原图删一条边之后是二分图。
于是，这个删一条边就可以用经典的删一分治来做，用可撤销并查集维护二分图的性质即可找到最后被删的边。
下面来介绍一个 \(O(n)\) 的做法。
显然我们需要删掉所有奇环交集上的边。
考虑一般图上找到所有环是困难的，所以我们不能从每条边找到包含他的奇环个数的角度考虑。
感性证明：
首先这种环空间，可以通过取一个生成树，然后由所有只经过一条非树边的环异或表示出来。
如果存在一种方案：那么一定会选被覆盖次数最多的（包括非树边，也有可能），并且这些被覆盖次数最多的环在树上的位置是等价的。（合法的是一段连续的路径）。
不过这样会被 \(hack\)，因为如果存在一个偶环，那么如果删掉的边是偶环上的，就可以通过异或这个偶环来绕开这条边（奇偶性一定不变，仍然是奇环），从而一定没用。
所以我们把所有被偶环覆盖的边都去掉，然后找剩下的里面被覆盖次数最多的，删掉。
之后跑二分图染色 \(check\) 一下即可。（其实应该是一定有解的）
！！！注意删掉一条边之后可能会不连通。所以我们从被删掉的边两个端点分别跑一次即可。
最后选的时候还要注意要让被删掉的边的两端点都被选上。
PS : 我在想这题的时候延伸想到的一个问题
判断一个边是否被一个简单奇环经过：图上简单路径，思考点双。由于一个点双内一定存在经过一个点和一个边的环，所以如果点双里存在一个奇环，找到另一个环连上去，由于路径一奇一偶，所以一定可以调整。
如果是不要求是简单路径，可以直接删掉这条边之后 \(dfs\)，维护奇数/偶数次经过。
构造方案：
考虑相当于找两个点不交路径。点/边不交可以考虑拆点，最大流。限制每个点上界是 \(1\)。跑最大流找到两条路径。
chatgpt 的严谨证明：
正确性证明
引理 1：合法答案等价于删去至多一条边后图为二分图
如果存在合法答案，那么除了最多一条 1-1 边以外，其他边全部是 0-1。
删去这条可能存在的 1-1 边后，剩余图就是二分图。
反过来，如果删去某条边后图是二分图，那么取删边后图的二分染色。原图中只有这条边可能变成同色边。
如果这条边是 0-0，全局取反即可变成 1-1。
所以两者等价。
引理 2：若删除非树边，则只有奇返祖边数量为 \(1\) 时可行
初始 DFS 染色下，所有树边都是异色边。
非树边中，只有奇返祖边是同色边。
如果奇返祖边数量大于 \(1\)，只删除其中一条，仍然会剩下其他同色边，因此不能直接靠删除一条非树边解决。
如果奇返祖边数量为 \(1\)，删去这唯一一条奇返祖边后，所有边都是异色边，图二分，合法。
引理 3：树边 \((parent[x],x)\) 合法当且仅当 odd[x] == K && even[x] == 0
翻转 \(x\) 子树后，一条非树边是否改变同色/异色状态，取决于它的树上路径是否经过树边 \((parent[x],x)\)。
- 奇返祖边原本同色，必须经过这条树边，翻转后才能变异色；
- 偶返祖边原本异色，不能经过这条树边，否则会变同色。
所以这条树边必须被所有奇返祖边路径覆盖，同时不能被任何偶返祖边路径覆盖。
这正是：
odd[x] == K && even[x] == 0
引理 4：算法不会漏解
根据引理 1，任意合法方案都等价于删除一条边后图二分。
被删除的边只有两种：
- DFS 树边；
- 非树边。
删除非树边的情况由 K == 1 覆盖。
删除树边的情况由树上差分条件 odd[x] == K && even[x] == 0 覆盖。
因此算法完整。