前言
前几天看到并查集的题目，竟然只会最简单的并查集，看来带权并查集和扩展域并查集还要是好好写个笔记复习复习的。
时间复杂度
如果仅仅使用路径压缩的并查集，时间复杂度似乎并不是\(O(\alpha(n))\)，详情见这里。
扩展域并查集
yxc给出了一种简单易懂的理解扩展域并查集的方式：将并查集中的元素看成一个个条件，两个元素在一个集合中的意义是：如果有一个条件，那么整个集合中的条件都成立。
我来形式化一点：并查集中的每一个元素都是一个语句\(p\)，每一个集合\(S\)都是一个命题：
\(如果p(p \in S)，那么q(q \in S,q\not=p)。\)
这样就十分容易理解了。
注：(x)指并查集中编号为x的元素。
我们定义：
- (x)表示第x个动物是A
- (x+n)表示第x个动物是B
- (x+2n)表示第x个动物是C
这样动物之间的关系就十分清晰了，合并的时候只需满足题意即可。
x和y同类：
- 如果(x)，那么(y)；如果(x+n)，那么(y+n)；如果(x+2n)，那么(y+2n)。
x吃y：
由于A吃B，B吃C，C吃A，所以：
- 如果(x)，那么(y+n)；如果(x+n)，那么(y+2n)；如果(x+2n)，那么(y)。
判断矛盾同理。
带权并查集
我们维护一个点到根节点的“距离”（这个“距离”是根据题意抽象得出的，而非真实的距离），以得出该点与集合中其它点的关系。
通常，关系有几种，距离就有几种，具体地，如果有\(n\)种关系，就有\(n\)种距离，为了方便，一般将距离定义为\([0,n-1]\)，这样可以使用取模运算方便地得出两点间相对关系。
还是上面的例题，这次使用带权并查集来做。
两只动物之间的关系只有3种，所以我们定义距离：
- 0：与根节点同类
- 1：被根节点吃
- 2：吃根节点
注：x->y意为x吃y
红色的边是根据题意的环形结构推理得出的。
所以，我们会发现当且仅当\(d_x + 1 \equiv d_y (mod 3)\)时，x吃y。
同类自然就不用讲，只要\(d_x \equiv d_y(mod 3)\)，x和y就同类。
判断矛盾同理。
维护\(d_x\)时，只需要暴力维护到根的权值之和即可。这为何是正确的呢？直观地理解，每一个结点都吃更深一层的结点，到了第3层，刚好完成一个循环，也就是第3层的结点和第0层的是同类，
而我们判断关系时又是在同余下处理的，所以自然是正确的。
需要注意的是，如果不做特殊处理，直接累加距离的话，可能会导致距离倍增并溢出。
解决办法有两个：
- 对\(d_x\)取模；
- 在更新\(d_x\)时，只累加\([0,n-1]\)的值（正余数）。
对比
扩展域并查集更加直观、易懂，不易写错，但是也有缺点，就是空间占用过多。
带权并查集关系较为复杂，用到了同余的知识，可能会吃数学的亏（like me），但是空间占用小。
题单
P2294 [HNOI2005]狡猾的商人
（带权并查集）