引入
$OI$ $Wiki$上看到的，感觉挺有意思的，最开始想要学这个是因为它能用来解决最小瓶颈路问题（至于为什么看这里：【OI杂记】求二叉树上任意两点的最短路径上的边权最大值）
我们先来看道货车运输：
$n$ 个点 $m$ 条无向边的图，$k$ 个询问，每次询问从 $u$ 到 $v$ 的所有路径中，最长的边的最小值。
$1leq nleq 15000,1leq mleq 30000,1leq kleq 20000$。
我相信你们看见这题的想法和我一样：
最小生成树上$LCA$一下就行了！时间复杂度 $O(mlog m+nlog n+klog n)$。（这里$LCA$用倍增。树链剖分复杂度是多一个 $log$ 的）
但是这题有另一种做法：$Kruskal$重构树（这种用到路径最长边值等一般都能用$Kruskal$重构树）
理解
$Kruskal$重构树是什么？和$Kruskal$求最小生成树有什么关系？
我们先来看一下$Kruskal$重构树的一些性质:
$Kruskal$重构树是由原图的 $n$ 个点，新添加的 $n-1$ 个点和 $2n-2$ 条边构成的树。
（以下讨论的$Kruskal$重构树都是最小$Kruskal$重构树，最大$Kruskal$重构树反之亦然）
下面是一个图和它的$Kruskal$重构树：（圆点是原图中的点，方点是新加的点）
它的性质有：
- 一棵二叉树
- 叶子结点都是原图中的点，没有点权；非叶子结点都是新加的点，有点权
- 旧点 $u,v$ 两点间（不包括 $u,v$）的所有节点（都是新点）的点权最大值为原图中 $u,v$ 两点间所有路径的最长边的最小值
- 新点构成一个堆（不一定是二叉堆），在最小Kruskal重构树中是大根堆（最大Kruskal重构树中是小根堆）
- 结合性质3和4，旧点 $u,v$ 两点的LCA（是新点）权值为原图中 $u,v$ 两点间所有路径的最长边的最小值
比如点 $1,3$ 的$LCA$权值为 $3$，恰好是原图中 $1,3$ 两点间所有路径的最长边的最小值（边 $(3,5)$）。
$Kruskal$重构树怎么求呢？
- 找到一条边权最小的，且没有被遍历过的边。
- 如果这条边连接的两个点目前没有在一个联通块，那么新建一个节点，点权为该边的边权，左右儿子设为这两个点的最远祖先。（通过设置儿子为最远祖先合并联通块且不破坏性质）
- 重复1,2直到遍历完所有的边。
画个图了解一下，下图中红点是该边连接的两个点，绿点和绿边是添加的点和边：
（这个图真的放不大，右键看大图）
如何用代码实现？像普通的$Kruskal$一样，维护一个路径压缩并查集，加点加边就可以了（又去看了遍路径压缩，之前好像并不理解）
回到原题：建出最小$Kruskal$重构树，每次$LCA$一下即可。
这里顺便说一下，如果原图不保证联通怎么办，如何预处理？（以下的代码中我也判了两点不连通的情况）
两点不连通可以用建$Kruskal$重构树中的并查集知道。而预处理，每次如果一个点没有$DFS$到，那么从这个点的最远祖先(根节点)$DFS$一遍（也可以用并查集知道）。
为什么要最远祖先呢？因为这样是对的且省时间，由于最小$Kruskal$重构树是大根堆，直接倒序$DFS$也是可以的
我还是直接用的倍增求$LCA$，也用树链剖分，可惜不会，这个坑还得去填
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 1e5+10; struct data{ int u, v, w; }edge[maxn]; bool cmp(data a, data b){ return a.w > b.w; } struct Edge{ int to, next; }e[maxn]; int n, m, q, u, v, w, tot, cnt = 0; int head[maxn], dep[maxn], val[maxn], f[maxn][21], fa[maxn]; //记得f数组后一维只用写到20几就可以了 int find(int x){ return x==fa[x] ? fa[x] : fa[x]=find(fa[x]); } void add(int u, int v){ e[++cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } void dfs(int u){ for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(v==f[u][0]) continue; //双向图需要判断是不是父亲节点 f[v][0] = u, dep[v] = dep[u]+1; dfs(v); } } //kruskal重构树 void kruskal(){ for(int i = 1; i <= n; i++) fa[i] = i; //并查集初始化 sort(edge+1, edge+1+m, cmp); tot = n; for(int i = 1; i <= m; i++){ int fu = find(edge[i].u), fv = find(edge[i].v); if(fu==fv) continue; val[++tot] = edge[i].w; fa[tot] = fa[fu] = fa[fv] = tot; add(fu, tot), add(tot, fu); //其实我们知道tot是根节点则不必建双向边,只保留add(tot, fu)即可 add(fv, tot), add(tot, fv); } //将无根树转化成有根树 (重构后tot是根节点,倒着dfs才能保证求出的lca是正确的) for(int i = tot; i >= 1; i--){ if(!dep[i]) dfs(i); } } int lca(int u, int v){ if(dep[u]<dep[v]) swap(u, v); int t = (int)(log(dep[u])/log(2)); for(int i = t; i >= 0; i--){ if(dep[f[u][i]]>=dep[v]) u = f[u][i]; if(u==v) return u; } for(int i = t; i >= 0; i--){ if(f[u][i]!=f[v][i]) u = f[u][i], v = f[v][i]; } return f[u][0]; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); kruskal(); for(int j = 1; (1<<j) <= tot; j++){ for(int i = 1; i <= tot; i++) f[i][j] = f[f[i][j-1]][j-1]; } scanf("%d", &q); for(int i = 1; i <= q; i++){ scanf("%d%d", &u, &v); if(find(u)!=find(v)) printf("-1 "); else printf("%d ", val[lca(u, v)]); } }
参考自：
https://oi-wiki.org/graph/mst/#kruskal_1
https://www.cnblogs.com/1000Suns/p/9360558.html（大多数文字图片来自这位博主，写的特别好）
https://www.luogu.com.cn/problemnew/solution/P1967
https://www.cnblogs.com/GavinZheng/p/10885933.html
https://www.luogu.com.cn/blog/mywd-ylyy/kruskal-zhong-gou-shu
https://www.cnblogs.com/zwfymqz/p/9683523.html