做了 cf 上一道题后发现我对并查集的理解不够深刻，顺带把带权并查集学一下。
并查集
初始化：对于一个集合 A 的所有元素，我们知道对于其中任意一个元素 i，i€A。此时，我们可以认为 i与 A 之间存在一条虚边，如果有新的元素要加入集合 A，将该元素与 A 建一条边即可。这条边我们用数组 fa[i] 表示，即点 i 和它的父亲。
加入：对于点 i，要加入点 j 所在的集合，怎么操作呢？fa[i]=fa[j] 即可。可如果我们要将两个集合合并呢？将集合 A 与集合 B 建边即可。这样做会导致什么结果呢？查询一个节点所属集合最坏可以达到O(n)的复杂度，所以我们增加 join 和 find 操作，join 就是将在两个集合之间建一条边，find 就是将集合间的边消除，让最终集合直接与点相连。
这就是并查集了。
带权并查集
假设存在多个集合，这些集合彼此之间又存在一些关系，
标签：元素,查集,fa,带权,集合,find From： https://www.cnblogs.com/buleeyes/p/17368255.html