kruskal重构树学习笔记
YDMaYi
·
·
个人记录
我太菜了，所以只能把我学习过程中遇到的困难解释清楚。有笔误请狠狠的撅我。
什么是 kruskal 重构树
既然叫做 kruskal 重构树，那么肯定和 kruskal 有关系。
在普通的 kruskal 算法中，每次都选取最小的合法边组成生成树，而 kruskal 重构树每次选取最小的合法边构建树。
（图片）
kruskal 重构树是一种恰有 n 个叶子结点，每个非叶子节点都恰有两个儿子节点的树。
那么这个树是怎么构建的呢？
相似地，将每条边按边权从小到大排序（因题目而异），每次选取边权最小的结点，新建一个点作为原边的两个子节点的各自父节点的父结点，kruskal 重构树没有边权，新建的结点的点权为原边的边权。
在维护这棵树的同时利用并查集维护连通块情况，以便判断剩下的边是否合法，以及新点插入时谁作它的子节点。
以 OI-wiki 上的图为例：
这个图的 kruskal 重构树是怎么来的呢？（方便起见，记连接 u 和 v 的边记作 (u, v) 或 (v, u)）
首先初始化时 fa[i] = i，重构树为空。
从边权最小的边开始，首先是 (1, 3)，发现 fa[1] = 1，fa[3] = 3，说明 1 和 3 不在同一个连通块中，就新建点 5，点 1 和 3 分别是它的两个子结点。（此时 fa[1] = 5，fa[3] = 5，fa[5] = 5，5 号点点权为 1）
再遍历到边 (2, 3)，发现 fa[2] = 2，而 fa[3] = 5。新建点 6 作为他们的父节点。此时 fa[1] = fa[3] = fa[2] = fa[6] = 6，点 6 的点权为 2。
再到边 (1, 2)，发现 fa[1] = fa[2] = 6，不合法，跳过这条边。
最后到边 (3, 4)，发现 fa[3] = 6，而 fa[4] = 4，新建点 7 作为他们的父节点，点 7 的点权为 4。现在所有点的 fa 都是 7。于是这棵树就构建完了。
构建完的树长这样：
那么这棵树构建出来有什么用吗？
kruskal 重构树的性质
来自 OI-wiki：
不难发现，原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。
也就是说，到点 x 的简单路径上最大边权的最小值 \leq val 的所有点 y 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。
我们在 Kruskal 重构树上找到 x 到根的路径上权值 \leq val 的最浅的节点。显然这就是所有满足条件的节点所在的子树的根节点。
如果需要求原图中两个点之间的所有简单路径上最小边权的最大值，则在跑 Kruskal 的过程中按边权大到小的顺序加边。
所以 kruskal 重构树经常配合 LCA 使用，可以用于解决限制走过路径中最小/大边权、求所需最小油量等问题。
P2245 星际导航
题目描述
$\text{sideman}$ 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 $(A, B)$，$\text{sideman}$ 想知道从顶点 $A$ 航行到顶点 $B$ 所经过的最危险的边的危险程度值最小可能是多少。作为 $\text{sideman}$ 的同学，你们要帮助 $\text{sideman}$ 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。
### 输入格式
第一行包含两个正整数 $N$ 和 $M$，表示点数和边数。
之后 $M$ 行，每行三个整数 $A$，$B$ 和 $L$，表示顶点 $A$ 和 $B$ 之间有一条边长为 $L$ 的边。顶点从 $1$ 开始标号。
下面一行包含一个正整数 $Q$，表示询问的数目。
之后 $Q$ 行，每行两个整数 $A$ 和 $B$，表示询问 $A$ 和 $B$ 之间最危险的边危险程度的可能最小值。
### 输出格式
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 $\text{impossible}$。
### 提示
对于 $40\%$ 的数据，满足 $N \leq 1000, M \leq 3000, Q \leq 1000$。
对于 $80\%$ 的数据，满足 $N \leq 10000, M \leq 10^5, Q \leq 1000$。
对于 $100\%$ 的数据，满足 $N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9$。数据**不保证**没有重边和自环。
---
求路径上所经过的边的边权最小值，想到 kruskal 重构树（但是这道题似乎不用也能做），重构完以后任意两点的 LCA 的点权就是途中的最大危险程度。
code（我不会树链剖分，所以写了倍增）：
```cpp
#include<bits/stdc++.h>
namespace IO {
inline int read() {
int ret = 0, f = 1;char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
ret = (ret << 1) + (ret << 3) + (ch ^ 48);
ch = getchar();
}
return ret * f;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
using namespace std;
const int maxn = 6e5 + 5;
const int maxm = 6e5 + 5;
const int maxp = 20 + 5;//倍增最大次幂
int n, m, A, B, Q;
int Edgetot;
struct Node {
int fr, to, val;
bool operator < (const Node & x) {
return x.val > val;
}
}Edge[maxm << 1];
void Edgeadd(int u, int v, int c) {
Edgetot++;
Edge[Edgetot].fr = u;
Edge[Edgetot].to = v;
Edge[Edgetot].val = c;
}
//以上是原图存储和操作，与链式前向星不同，存了每条边的端点和权值
int tot, hd[maxn], to[maxm << 1], nxt[maxm << 1], val[maxn << 1];
void add(int u, int v) {
tot++;
nxt[tot] = hd[u];
hd[u] = tot;
to[tot] = v;
}
//以上是重构树部分
int fa[maxn << 1], k;
int Find(int x) {
return (x == fa[x]) ? x : fa[x] = Find(fa[x]);
}
int dep[maxn], fat[maxn][maxp];
int Posval[maxn << 1];
void dfs(int x, int father) {
dep[x] = dep[father] + 1;
fat[x][0] = father;
for (int i = 1;i < maxp;i++) fat[x][i] = fat[fat[x][i - 1]][i - 1];
for (int i = hd[x];i;i = nxt[i]) {
int v = to[i];
if (v == father) continue;
dfs(v, x);
}
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = maxp - 1;i >= 0;i--) if (dep[x] - (1 << i) >= dep[y]) {
x = fat[x][i];
}
if (x == y) return x;
for (int i = maxp - 1;i >= 0;i--) if (fat[x][i] != fat[y][i]) {
x = fat[x][i];
y = fat[y][i];
}
return fat[x][0];
}
int main() {
n = read(), m = read();
for (int i = 1;i <= m;i++) {
int u = read(), v = read(), c = read();
Edgeadd(u, v, c), Edgeadd(v, u, c);
}
sort(Edge + 1, Edge + 1 + m * 2);
for (int i = 1;i <= n * 2;i++) fa[i] = i;k = n;
for (int i = 1;i <= m * 2;i++) {
int u = Edge[i].fr, v = Edge[i].to, Val = Edge[i].val;
int Fau = Find(u), Fav = Find(v);
if (Fau == Fav) continue;
k++, fa[Fau] = k, fa[Fav] = k;
add(k, Fau),add(k, Fav);
Posval[k] = Val;
}
for (int i = 1;i <= k;i++) if (fa[i] == i) dfs(i, 0);
Q = read();
while (Q--) {
int A = read(), B = read();
if (Find(A) != Find(B)) puts("impossible");
else write(Posval[LCA(A, B)]), putchar(10);
}
return 0;
}
```