2022/07/12 做题记录

模拟赛 T2

http://47.92.197.167:5283/contest/240/problem/2

首先求出一棵 dfs 树，把要割的变分成树边和非树边两类，存在一个结论：

如果存在一个割掉的边的子集，使所有没被割掉的非树边都覆盖了偶数条在这个集合内的树边，那么这种割边方案可以使原图不连通。

必要性：对于任何能将原图分为两个以上部分的割集，考虑原集合的极小，且也能将原图割开的子集（这个子集一定能将原图恰好分成两个集合），我们标记它其中的所有树边，从任何一个节点开始走只走树边，如果走过一条被标记的边，那么说明切换了一次点所在的集合，这样如果一条没被割掉非树边覆盖了奇数条被割掉的边，那么说明它连接的两个点属于不同集合，这是不可能的。

充分性：类似的，通过以上的方式我们可以求出这两个集合具体都有哪些点，如果没有一条没被割掉的非树边能连接这两个集合，那么这两个集合就是隔开后会被分开的两部分，所以原割集一定合法。

考虑怎么判定一个割集是否合法，给每一条非树边随机一个权值，而一条树边的权值就是所有覆盖了它的非树边权值的异或和，那么一个割集中如果有一个边的子集异或和为 0 ，那么这个割集是合法的：假如我们没有割非树边，那么这个条件就等价于“使所有没被割掉的非树边都覆盖了偶数条在这个集合内的树边”，而能在这个子集内选非树边的原因是一条已经被割掉的非树边也可能覆盖了奇数条边，会给异或和提供贡献（它的边权），而我们已经把它割掉了，这不需要考虑，所以这是为了给我们一种方式去除它的贡献（因为把它选上对答案的贡献也是它的边权，可以抵消）。

code: onedrive 出了点问题，暂时没传