kruskal重构树

简介

在 $kruskal$ 求最小生成树的过程中，每次加边时，新建一个节点，然后让两个连通块分别成为新建节点的左右儿子，且新建节点的点权就是这条边的边权

这棵树有几个性质：

是一个二叉树
是一个类似大根堆（小根堆）的东西，满足父节点的值大于等于儿子节点的值
原图上任意两点的所有路径中的最长边的最小值为其 $lca$ 的值（或者是最短边中的最大值
原图中的所有节点都是叶子节点

int main() { 
    for (int i = 1; i <= m; ++i) {
        int u = E[i].fr, v = E[i].to, w = E[i].w, fu, fv; 
        if ((fu = find(u)) == (fv = find(v))) continue;
        fa[fu] = fa[fv] = ++top; T[top].ch[0] = fu; T[top].ch[1] = fv; 
        T[top].v = w;
    }
}

例题

简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，点 $i$ 个初始点权为 $w_i$，$w_i$ 构成了一个 $[1,n]$ 的排列，现在有 $q$ 次操作，操作有两种，第一种操作给定 $v$，查询与 $v$ 相连的点中点权最大的点的点权，然后点权最大的这个点的点权置为 $0$；第二种操作给定一个整数 $i$，将第 $i$ 条边删掉

简要题解：我们考虑离线按照边被删掉的时间做一个 $kruskal$ 重构树，这样我们每次查询与点 $u$ 相连的点是 $kruskal$ 重构树上的一个点的子树，那么我们现在的操作相当于区间查询和单调修改，使用线段树即可，时间复杂度 $O(n\log n)$

CF 1416D Graph and Queries
简要题意：给定一棵 $n$ 个点的树，现在有 $m$ 次操作，操作有三种，操作一给定一个区间 $[l,r]$，将编号在 $[l,r]$ 内的点都染成白色；操作二给定一个区间 $[l,r]$，将编号在 $[l,r]$ 内的点都染成黑色；操作三给定一个点 $x$，求 $x$ 到黑点的最大瓶颈距离，要求是简单路径，且不包括 $x$，不存在输出 $-1$，初始时所有点都是白色

$n,m\le 3\times 10^5$

简要题解：最大瓶颈距离我们考虑 $kruskal$ 重构树，那么现在操作三转换为求 $x$ 和所有白点的 $lca$ 中深度最小的那个，容易得到这相当于 $x$ 与所有白点的 $lca$ 的 $lca$，那么我们直接用线段树维护 $lca$ 就行了

时间复杂度 $O(n\log n)$

CF 1628E Groceries in Meteor Town
简要题意：给定一个 $n\times n$ 四连通网格图，有一些位置有障碍，现在有 $m$ 次询问，每次询问给定起点 $(x_1,y_1)$ 和终点 $(x_2, y_2)$，求一个最大的 $k$，满足存在一个从起点到终点的路径，使得路径上的每个点到离它最近的障碍点切比雪夫距离小于 $k$

$n\le 1000,m\le 3\times 10^5$

简要题解：我们定义每个非障碍点的点权为这个点距离最近的障碍点的切比雪夫距离，那么我们每次相当于要求一个瓶颈路径，直接上 $kruskal$ 重构树即可

时间复杂度 $O(n^2\log n+m\log n)$

Luogu P3684 [CERC2016]机棚障碍 Hangar Hurdles