Kruskal 重构树学习笔记

Kruskal 重构树是一种常用于维护连通性的数据结构,用它可以快速维护一些点要联通的瓶颈边权之类的问题。

先看一道例题:CF1706E Qpwoeirut and Vertices

给一张 nn 个点 mm 条边的无向连通图,qq 次询问,每次询问给一个区间 [l,r][l,r],求按照输入顺序加边,至少加到第几条边可以令编号在 [l,r][l,r] 内的点连通。

2n1052\le n\le 10^51m,q2×1051\le m,q\le 2\times 10^5

首先让所有点都单独自己一个连通块,并且让每个连通块的根节点都为连通块内的那个点本身

然后按照边输入的顺序合并边两头的节点所在的连通块,处理到第 ii 条边时:

  1. 若这条边两头的节点已经连通,那么跳过这次操作;
  2. 设两个连通块的根节点分别是 rxrxryry,那么就新建一个连向两个连通块的新点 rr',连接 rrxr'\to rxrryr'\to ry
  3. tmer=itme_{r'}=i,即记录下 rr' 新建的时间点;
  4. 最后合并两个连通块,新的连通块的根节点即为 rr'

其实就是相当于把 Kruskal 求最小生成树时的合并操作表达成树。

容易发现,这样建出来的是一棵二叉树,并且有一些美妙的性质:

  • 叶子节点就是原图中的每个点,新建出来的点代表原图的建边顺序最小生成树中的边;
  • 对于所有满足 vvuu 子树内的节点的 vv,都有 tmev<tmeutme_v<tme_u
  • 原图中的一个点集 SS 连通至少要加前 tmelca(S)tme_{\operatorname{lca}(S)} 条边

我们就把这样的二叉树叫做 Kruskal 重构树。那么本题直接用线段树维护 Kruskal 重构树上的区间 lca\operatorname{lca} 即可。

建树代码:

for(int i=1;i<=n*2-1;i++) fa[i]=i;
for(int i=1;i<=n*2-1;i++) ls[i]=rs[i]=tme[i]=0;
int cnt=n;
for(int i=1;i<=m;i++)
{
    int x,y;
    scanf("%d%d",&x,&y);
    int rx=fnd(x),ry=fnd(y);
    if(rx!=ry)
    {
        int u=++cnt;
        tme[u]=i;
        ls[u]=rx;
        rs[u]=ry;
        fa[rx]=fa[ry]=u;
    }
}

练习题目