例

有一个 $n$ 个数的序列只由0，1组成，$m$ 个条件，每个条件告诉区间 $[l,r]$ 有奇数个1还是偶数个1，判断是否会出现矛盾。

每个条件可转化为 $sum[r]-sum[l-1]$ 是奇数还是偶数，即 $sum[l-1]$ 与 $sum[r]$ 的奇偶性是否相同。

边带权

边权 $d[x]$ 为0表示与父亲奇偶性相同，为1表示奇偶性不同，多次异或可得到 $x$ 与根的关系。

在父亲合并时，要注意父亲到新父亲的d怎么计算，因 $d[x]\ xor\ d[y]\ xor\ d[p]=ans$ ，故 $d[p]=ans\ xor\ d[x]\ xor\ d[y]$ 。

text

1
2
3
4
5
6
7
int getfa(int x)
{
	if(x==fa[x])return x;
	int rt=getfa(x);
	d[x]^=d[fa[x]];
	return fa[x]=rt;
}

拓展域

把每个节点拆成两个节点 $x_{odd}$ 与 $x_{even}$ ，若 $sum[x]$ 与 $sum[y]$ 奇偶性相同，那么分别合并 $y_{odd},x_{odd}$ 与$y_{even},x_{even}$ ，否则分别合并 $y_{even},x_{odd}$ 与 $y_{odd},x_{even}$ ，然后判断矛盾即可。