Kruskal 重构树学习笔记

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

先看一道例题：CF1706E Qpwoeirut and Vertices。

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

$2\le n\le 10^5$，$1\le m,q\le 2\times 10^5$。

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

然后按照边输入的顺序合并边两头的节点所在的连通块，处理到第 $i$ 条边时：

1. 若这条边两头的节点已经连通，那么跳过这次操作；
2. 设两个连通块的根节点分别是 $rx$ 和 $ry$，那么就新建一个连向两个连通块的新点 $r'$，连接 $r'\to rx$ 和 $r'\to ry$；
3. 令 $tme_{r'}=i$，即记录下 $r'$ 新建的时间点；
4. 最后合并两个连通块，新的连通块的根节点即为 $r'$；

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

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

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

我们就把这样的二叉树叫做 Kruskal 重构树。那么本题直接用线段树维护 Kruskal 重构树上的区间 $\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;
    }
}

练习题目

• P4197 Peaks

• P7834 [ONTAK2010] Peaks 加强版