并查集扩展（带权/种类/树上并查集）

· · 个人记录

带权并查集

带权并查集指在并查集的边上定义某种权值，并在路径压缩的过程中更新。

模板题：UVA1329 Corporative Network

定义 d_x 表示点 x 到所在并查集根节点的距离，每次查询点 x 前都进行一次 getfather(x) 更新 d_x 即可。

核心代码：

int gf(int x){
    if(f[x]==x)return x;
    int y=gf(f[x]);
    return d[x]+=d[f[x]],f[x]=y;
}

习题：

P2294 [HNOI2005]狡猾的商人

P1196 [NOI2002] 银河英雄传说

种类并查集

种类并查集本质上就是拆点。种类并查集的题目通常也可用带权并查集解决，但种类并查集更直观。

模板题：P2024 [NOI2001] 食物链

对每个动物 x 拆出三个点 x_a,x_b,x_c，分别表示 x 的种类是 a,b,c，然后按照题意用并查集模拟即可。

习题：

P5787 二分图 /【模板】线段树分治

CF776D The Door Problem

CF1290C Prefix Enlightenment

树上并查集

树上并查集利用并查集实现树上的路径压缩，以优化跳 father 的时间复杂度。

和一般的并查集不同，树上并查集必须儿子向父亲合并，所以不能按秩合并，一般的实现复杂度是 O(n\log n)，但最快可以做到线性。参考 RMQ标准算法和线性树上并查集。

模板题：P4092 [HEOI2016/TJOI2016]树

将操作离线，倒序处理，删掉点 x 的标记就相当于将 x 向 fa_x 合并，查询点 x 祖先的第一个标记就是查询 x 所在并查集的根节点。

习题：

P4434 [COCI2017-2018#2] Usmjeri

P6963 [NEERC2017]Laminar Family

P5344 【XR-1】逛森林 题解