bzoj3569
题意：
加入删除边后判断整个图是否联通。
共价大爷？
首先因为是判断整个图连通性，肯定是存在性质，一定会避免所谓动态图连通性。
似乎存在若干 \(O(q\cdot \mathrm{poly(k)}\cdot \mathrm{polylog})\) 的做法。（有的能过有的不能） 。
而这个题的正解是一个结论：先建出任意一颗生成树，然后将非树边随机赋值，树边权值是覆盖上的非树边异或和，那么对于给出的删除边集，当且仅当有一个子集使得异或和=0。
step1 （定义）
首先我们考虑一组割边集 \(E\)，记它所对应的一侧的点集为 \(s(E)\)。
形式化的说：\(E=\{(u,v)\mid u\in s(E),v\in V-s(E)\}\)。
可以说明，\(s(E_1\oplus E_2)=s(E_1)\oplus s(E_2)\)。
如图： 
。
这样启示我们实际上这个割边集也是存在基的。。。
而实际上割边的基就是对于一条树边 \((u,v),dep(u)<dep(v)\) 子树 \(u\) 与其外部组成的割边集就是基，考察这些一定不是线性相关的（都只包含一条树边）。
割边空间记作 \(\mathcal{D}\).
其次我们考虑一个回路（环），这个和cf1515G 是一样的，对于一个无向图的回路集合实际上就是由所有一条非树边组成的环线性表示的。也就是回路的基是一条非树边形成的环。
以上两种边集基极大的说明都可以归纳。
记两个边集的点积：\(a\cdot b=|a\& b|\bmod 2\) 。不难发现点积对异或运算有分配率。
\((a\oplus b)\cdot c=(a\cdot c)\oplus(b\cdot c)\)。
回路空间记作 \(\mathcal{C}\).
step2 证明
lemma1
\(\forall c\in\mathcal{C},d\in \mathcal{D}\to c\cdot d=0\)。
证明：因为 \(\mathcal{C,D}\) 都是线性空间。并且点积对于异或有分配律，所以只考虑基即可。
考虑 \(d_i\) 只有两半，\(c\&d\) 后只剩割边。又因为每次走割边交换所在集合。
所以得证。
所以现在只需要对一个给定的割边集合，对所有的回路做点积，看大小是不是0。
由于点积性质，我们只需要对基做一遍即可。
那么考虑实际含义，我们希望每个基和割边集交 mod 2 = 0。
也就是说每一个基环上面有偶数个集合里的。
这样我们把非树边随机选，树边设成覆盖他的非树边异或和，这样做的正确性就显然了。
dls的说明我好像更能理解。。。
就是这个操作实际上就是在把一个环 xor w。
- 首先考虑任意一个点他的邻边xor=0，等价于任意一条树边=覆盖他的非树边的xor。
因为如果一条边 \(e\) 不在任意一条环上，那么他的权值是0，否则若 \(e\) 在环 \(c\) 上，\(v\to u\),那么 \(u\) 也必然有一条出边，所以xor抵消了。
另外一半可以一个一个加入非树边说明。
- 任何一个子图的点权xor就是割边的xor。
考虑 \(A\to A\) 会被算两遍，\(A\to B\) 恰好是割边。
所以的证了。