首先解释一下什么叫“多种传递关系”：
普通的并查集只能维护“朋友的朋友是朋友”，而面临“敌人的敌人是朋友”的情况十分乏力，多种传递关系即指“敌人的敌人是朋友”类情况。
我们首先看这样一个问题：
我们考虑将一段区间的奇偶性转化为前缀和形式，设 \(s_i\) 表示第 \(i\) 位的前缀和，则当区间 \([l,r]\) 有奇数个时，\(s_{l-1}\) 与 \(s_r\) 奇偶性不同，有偶数个时相同，这样可以转化为一个可以并查集处理的东西。
但稍加思索我们会发现这里有多种传递关系，不是单纯的在或不在一个集合里：
-
\(i\) 与 \(j\) 奇偶性相同，\(j\) 与 \(k\) 奇偶性相同，则\(i\) 与 \(k\) 奇偶性相同。
-
\(i\) 与 \(j\) 奇偶性相同，\(j\) 与 \(k\) 奇偶性不同，则\(i\) 与 \(k\) 奇偶性不同。
-
\(i\) 与 \(j\) 奇偶性不同，\(j\) 与 \(k\) 奇偶性不同，则\(i\) 与 \(k\) 奇偶性相同。
对于这种多种传递关系问题，有两种方法。
边带权并查集
我们知道，并查集是一个树形结构，所以我们可以将边加上边权，设 \(d_i\) 为第 \(i\) 位与 \(fa_i\) 之间的边权。
对于上面的题，注意到传递关系与异或十分相似，于是有 \(d_i=0\) 时，\(i\) 与 \(fa_i\) 奇偶性相同，\(d_i=1\) 时，\(i\) 与 \(fa_i\) 奇偶性不同（反过来也行）。判断时，判断两点 \(d\) 值异或的结果是否与给出结果对应即可。（只计算两点边权的的原因是并查集缩到最简形态一定是菊花，两个边权相邻成为一条链）。
对应的，\(\operatorname{find}\) 函数也会发生一些改变：
int find(int x){
if(fa[x]==x) return x;
int fx=find(fa[x]);
d[x]^=d[fa[x]];//这里增加了一条维护边权的语句，根据情况更改
return fa[x]=fx;
}
对于两个点不在一个集合里的情况，我们往往可以通过一些手段知道两个树形结构根之间应该取的边权，仍以这一题为例，由于不在一个即合理所以这条关系默认成立，设合并的两个并查集根为 \(p\)，\(q\)，将 \(p\) 合并到 \(q\)，即有 \(ans=d_x \operatorname{xor} d_y \operatorname{xor} d_p\)，移项得 \(d_p=d_x \operatorname{xor} d_y \operatorname{xor} ans\)，问题解决。
扩展域并查集
我们考虑开两个并查集，分别表示“朋友”与“敌人”关系。
对于关系不确定的两个点，我们尝试带入两个并查集，寻找合法的关系决定他们的状态。
说一下上面那道题的解法：
开两个并查集，分别代表 \(s_x\) 为奇数与 \(s_x\) 为偶数，称为奇数域和偶数域，写为 \(x_o\) 与 \(x_e\)，假设目前处理 \(x\) 与 \(y\) 的关系。
若偶数个，则合并 \(x_o\)，\(y_o\) 与 \(x_e\)，\(y_e\)。
若奇数个，则合并 \(x_o\)，\(y_e\) 与 \(x_e\)，\(y_o\)。
判断合法同理。
可能有人对如何合并两个并查集里的东西有点疑问：
我们开在一个数组里就好了。
个人感觉一般情况下扩展域更好想点。
标签：关系,多重,浅谈,边权,查集,奇偶性,fa,operatorname From： https://www.cnblogs.com/victoryang-not-found/p/17135681.html