Kruskal 重构树是一种常用于维护连通性的数据结构,用它可以快速维护一些点要联通的瓶颈边权之类的问题。
先看一道例题:CF1706E Qpwoeirut and Vertices。
给一张 个点 条边的无向连通图, 次询问,每次询问给一个区间 ,求按照输入顺序加边,至少加到第几条边可以令编号在 内的点连通。
,。
首先让所有点都单独自己一个连通块,并且让每个连通块的根节点都为连通块内的那个点本身。
然后按照边输入的顺序合并边两头的节点所在的连通块,处理到第 条边时:
- 若这条边两头的节点已经连通,那么跳过这次操作;
- 设两个连通块的根节点分别是 和 ,那么就新建一个连向两个连通块的新点 ,连接 和 ;
- 令 ,即记录下 新建的时间点;
- 最后合并两个连通块,新的连通块的根节点即为 ;
其实就是相当于把 Kruskal 求最小生成树时的合并操作表达成树。

容易发现,这样建出来的是一棵二叉树,并且有一些美妙的性质:
- 叶子节点就是原图中的每个点,新建出来的点代表原图的建边顺序最小生成树中的边;
- 对于所有满足 是 子树内的节点的 ,都有
- 原图中的一个点集 连通至少要加前 条边;
我们就把这样的二叉树叫做 Kruskal 重构树。那么本题直接用线段树维护 Kruskal 重构树上的区间 即可。
建树代码:
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;
}
}