证明一下边带权做法的充分性
我们考虑异或和
对一个01序列，我们做一个异或前缀和，设为\(sum_n\)，那么\(a_i=sum_i\enspace xor\enspace sum_{i-1}\)
对任何时刻的没有产生矛盾的并查集森林，我们随便给每个森林的根节点赋值一个0或1，那么其他所有节点的值也能够推导出来（注意中途不可能重复赋值，因为一个点只属于一个集合），如果序列中还剩余一些点没有赋值，就随便赋0或1，然后赋的值作为异或前缀和，就可以推导出来一个符合条件的01序列了
在讨论一下扩展域的做法，一般来说扩展域都可以这么理解
就像蓝书上面说的一样，\(x_{odd}\)和\(x_{even}\)分别表示\(x\)是奇数和偶数，那么连接就代表可以互相推出
我们以前忽略的最严重的一点是，连接后的森林，他是完全对称的，就像下面这样（其中一个方框代表一个并查集集合）
那么对于一个还没有产生矛盾的森林，我们依次对每一排（注意是每一排）的其中一个赋值就好了，比如上图，我们考虑第一排，令\(x\)是奇数，推出\(y\)是偶数，然后右边那个方框就不用管了，令\(i\)是偶数，推出\(j\)是奇数，左边那个方框就不用管了
同边带权，这样对任意一个没有出现矛盾的森林都可以找到一个合法的序列（矛盾指\(x_{odd}\)和\(x_{even}\)在同一个连通块里面）
而合并时只用像蓝书说的那样合并就好了
这也解释了为什么代码里面只用判断一边关系就可以说明是否矛盾
标签：奇偶,sum,异或,方框,game,序列,森林,赋值 From： https://www.cnblogs.com/dingxingdi/p/17893512.html