概述
$\text{Kruskal}$ 重构树是基于 $\text{Kruskal}$ 最小生成树算法的一种算法，它主要通过将边权转化为点权来实现，其中有一些非常奇妙的性质！
构造
除了连边，其他过程都和 $\text{Kruskal}$ 最小生成树算法完全一样。
当我们需要在 $u,v$ 之间连一条权值为 $w$ 的边时，$\text{Kruskal}$ 重构树算法是这样实现的：
- 新建节点 $x$，将 $x$ 的点权设为 $w$。
- 设 $u,v$ 所属集合分别为 $S_u$ 和 $S_v$，那么连边 $(x,S_u)$ 和 $(x,S_v)$，此处连有向边即可，注意没有边权！
- 将 $u$ 和 $v$ 所属集合都改为 $x$。
其余过程直接套用 $\text{Kruskal}$ 即可！
重构树的根应该为 $2n-1$，也就是最后一个点。原因为：如果以 $1\sim n$ 中的任何一个点作为根会破坏重构树的形态；连边时向下连边，只有以 $2n-1$ 为根时才能遍历整棵树。
构造重构树的复杂度和 $\text{Kruskal}$ 一样，都是 $\mathcal O(n\log n)$。
性质
最后形成一棵有 $2n-1$ 个节点的树。
我们需要将 $n$ 个原来的点最后放到同一个集合中，那么需要进行 $n-1$ 次合并。每次合并都会新建 $1$ 个节点和 $2$ 条无向边。那么一共会有 $2n-1$ 个点和 $2n-2$ 条边。
重构树中的叶子节点为原树中的节点，其余每个节点代表了一条边。
我们每次将 $x$ 和下方的 $u,v$ 连边，这个证明很显然吧！
原树 $u$ 到 $v$ 路径上的边权最大值为重构树上 $u$ 和 $v$ 的 $\text{LCA}$ 的点权。
根据 $\text{Kruskal}$ 的过程，我们把边按照权值从小到大排序，那么对于所有非叶子节点，它的点权（原图的边权）一定不大于父亲节点的点权，所以路径上的最大值即为 $\text{LCA}$ 的点权。
例题
本文以「BZOJ 3732」Network 为例（虽然此题可以直接用倍增解决，但是这里使用 $\text{Kruskal}$ 重构树的方法实现）
Description
给你 $n$ 个点 $m$ 条边的无向图，每条边的长度为 $d_i$。现在有 $k$ 个询问 ，每次询问 $u,v$ 之间的所有路径中，最长边的最小值是多少？
数据范围：$1\le n\le 1.5\times 10^4$，$1\le m\le 3\times 10^4$，$1\le k\le 2\times 10^4$，$1\le d_i\le 10^9$
Solution
首先我们可以发现一个性质：最长边最小的路径一定在这张图的最小生成树上。那么我们只要求出这张图的最小生成树，然后倍增求出最大值即可。
然而现在不是讨论倍增的时候！
我们不建立最小生成树，而是建立重构树。根据上面的性质 $(3)$，每次询问的答案就是 $\text{LCA}(u,v)$ 的点权。
时间复杂度：$\mathcal O(m\log m+k\log n)$
Code
#include <cstdio>
#include <algorithm>
const int N = 3e4 + 5, M = 6e4 + 5, logN = 16;
int n, m, q, tot, fa[N], lnk[N], ter[M], nxt[M], val[N], f[N][logN], dep[N];
struct Edge {
int u, v, w;
bool operator<(const Edge &b) const {
return w < b.w;
}
} e[M];
void add(int u, int v) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void kruskal() {
std::sort(e + 1, e + m + 1);
int lim = n + n;
for (int i = 1; i <= lim; i++) fa[i] = i;
for (int idx = n, i = 1; i <= m; i++) {
int fu = find(e[i].u), fv = find(e[i].v);
if (fu == fv) continue;
fa[fu] = fa[fv] = ++idx, val[idx] = e[i].w;
add(idx, fu), add(idx, fv);
if (idx == lim - 1) break;
}
}
void dfs(int u, int p) {
dep[u] = dep[p] + 1, f[u][0] = p;
for (int i = 1; (1 << i) <= dep[u]; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (v == p) continue;
dfs(v, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) std::swap(u, v);
int d = dep[u] - dep[v];
for (int i = 15; ~i; i--) if (d & (1 << i)) u = f[u][i];
if (u == v) return u;
for (int i = 15; ~i; 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%d", &n, &m, &q);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}
kruskal();
dfs(n + n - 1, 0);
for (int i = 1; i <= q; i++) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", val[lca(u, v)]);
}
return 0;
}