bzoj 3569 DZY Loves Chinese II

题意:给一个n个点m条边的(连通)无向图,q个询问,每次询问给出k条原图中的边,问将这些边删掉后,无向图是否还是保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。\(N\le 100000,M\le 500000,Q\le 50000,1\le K\le 15\)。

这道题实际上是bzoj 3237的加强版。

对原图随便找一个生成树出来,对非树边随机边权,树边边权则为覆盖它的所有非树边权值的异或和,那么一个边集删去后使得图不连通等价于这个边集存在一个子集的权值异或和为0。

随机是为了让边权异或和在不应该是0的情况下不为0。

正确性证明参考这篇 http://dwjshift.logdown.com/posts/2830435

时间复杂度\(O(m+n+32qk)\)