带权并查集
本质上就是并查集树上的边有了边权，进而可以用一个 \(dist\) 数组来表示每个点与其所在集合的祖先之间的关系；
- 合并：在任意两个点有了新的关系后，可以通过直接合并二者所在集合的祖先来构建二者之间的关系；
- 查询：查询同一集合内任意两点之间的关系也可以通过二者和祖先之间的关系推导出来；不同集合内的两个点是没有任何关系的
- 在查询每个点的祖先（find）过程中，边做路径压缩，边合并 dist 的信息
可以用来解决 维护并查集每个集合内任意两点之间信息 的问题。
模板：
// 带权并查集
int fa[100002], siz[100002];
int dist[100002];
void init(int n){for(int i = 1; i <= n; i ++){fa[i] = i;dist[i] = 0;siz[i] = 1;}
}
int find(int x){ // 路径压缩的同时，合并dist的信息if(x != fa[x]){int tmp = fa[x];fa[x] = find(tmp);dist[x] += dist[tmp];}return fa[x];
}
bool union_(int l, int r, int k){ // 设置 l 到 r 在一维数轴上的距离为 vint lf = find(l), rf = find(r);if(lf != rf){ // 只有二者不在同一个集合中才能合并fa[lf] = rf;siz[rf] += siz[lf];siz[lf] = 0;dist[lf] = dist[r] - dist[l] + k;return true; }return false;
}
int query(int u, int v){ // 查询 u 与 v 之间的相对距离（只有u, v在同一集合中才有解）if(find(u) != find(v)) return INF;return dist[u] - dist[v];
}
扩展域并查集
本质上就是好几个并查集，其中每个并查集用于表示某个种类。一个个体可以是这几个种类中的某一种，而种类之间可能存在着一些关系；而题目并不给出这些个体是哪个种类，而会给出每一对个体之间的关系。这时就可以通过枚举这两个个体可能的所有种类的情况，并将其合并起来。
举个例子：有 3 种动物种类 \(A,B,C\)，三者形成一种循环食物链：A 吃 B，B 吃 C，C 吃 A。
则我们需要对于每个种类均初始化一个并查集，而不同并查集内的个体是需要参与合并的。
现在有两个动物 x, y， 规定 x 吃 y，那么，我们需要做：
- A 中的 x 与 B 中的 y 合并
- B 中的 x 与 C 中的 y 合并
- C 中的 x 与 A 中的 y 合并
而若想查询 z 是否吃 w，或者检验某个规定是否与之前的规定产生矛盾，就可以直接利用上面维护的扩展域并查集来检查。更详细的可以看这篇博客：blog