定义
在跑 $Kruskal$ 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。
首先新建$n$个集合，每个集合恰有一个节点，点权为$0$。
每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。
不难发现，在进行$n-1$轮之后我们得到了一棵恰有$n$个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 $Kruskal$ 重构树。
性质
不难发现，原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = $Kruskal$ 重构树上两点之间的 $LCA$ 的权值。
也就是说，到点$x$的简单路径上最大边权的最小值$\leq val$的所有点$y$均在 $Kruskal$ 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。
我们在 $Kruskal$ 重构树上找到$x$到根的路径上权值$\leq val$的最浅的节点。显然这就是所有满足条件的节点所在的子树的根节点。
如果需要求原图中两个点之间的所有简单路径上最小边权的最大值，则在跑 $Kruskal$ 的过程中按边权大到小的顺序加边。
练习
$kruskal$模版题
题目描述
给定一张 $n$ 个点、$m$ 条边的无向图，第 $i$ 个点的权值为 $a_i$，边有边权。
有 $q$ 组询问，每组询问给定三个整数 $u, x, k$，求从 $u$ 开始只经过权值 $\leq x$ 的边所能到达的权值第 $k$ 大的点的权值，如果不存在输出 $-1$。
思路
首先建立大根堆的$Kruskal$ 重构树，用可持久化权值线段树维护权值第 $k$ 大，查询时我们倍增到权值$\leq x$ 的最浅的节点，然后查询以该节点为根节点的子树内叶子结点权值第 $k$ 大。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, q, h[N];
int rt[N], ls[N << 5], rs[N << 5], cnt[N << 5], tot;
void Insert(int &x, int y, int l, int r, int p) {
x = ++ tot;
cnt[x] = cnt[y] + 1;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
if (p <= mid) {
rs[x] = rs[y];
Insert(ls[x], ls[y], l, mid, p);
} else {
ls[x] = ls[y];
Insert(rs[x], rs[y], mid + 1, r, p);
}
}
int Query(int x, int y, int l, int r, int k) {
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
int rcnt = cnt[rs[x]] - cnt[rs[y]];
if (k <= rcnt) {
return Query(rs[x], rs[y], mid + 1, r, k);
}
return Query(ls[x], ls[y], l, mid, k - rcnt);
}
struct Edge {
int u, v, w;
bool operator < (const Edge &o) const {
return w < o.w;
}
};
int f[N][20], val[N], dep[N], dfn[N], siz[N], rk[N], ed[N];
int find(int x) {
return f[x][0] == x ? x : f[x][0] = find(f[x][0]);
}
vector< int > adj[N];
void dfs(int x, int p) {
f[x][0] = p;
for (int i = 1; i <= 19; ++ i) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
dep[x] = dep[p] + 1;
dfn[x] = ++ dfn[0];
rk[dfn[x]] = x;
for (const auto &y : adj[x]) {
if (y ^ p) {
dfs(y, x);
siz[x] += siz[y];
}
}
ed[x] = dfn[0];
if (!siz[x]) {
siz[x] = 1;
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> q;
vector< int > vec;
for (int i = 1; i <= n; ++ i) {
cin >> h[i];
vec.push_back(h[i]);
}
for (int i = 1; i <= n * 2 - 1; ++ i) {
f[i][0] = i;
}
sort(begin(vec), end(vec));
vec.erase(unique(begin(vec), end(vec)), end(vec));
for (int i = 1; i <= n; ++ i) {
h[i] = lower_bound(begin(vec), end(vec), h[i]) - begin(vec) + 1;
}
vector< Edge > g;
for (int i = 1; i <= m; ++ i) {
int u, v, w;
cin >> u >> v >> w;
g.push_back({u, v, w});
}
sort(begin(g), end(g));
int cnt = n;
for (const auto &[u, v, w] : g) {
int fx = find(u), fy = find(v);
if (fx != fy) {
++ cnt;
f[fx][0] = f[fy][0] = cnt;
val[cnt] = w;
adj[cnt] = {fx, fy};
}
}
dfs(cnt, 0);
for (int i = 1; i <= dfn[0]; ++ i) {
rt[i] = rt[i - 1];
if (rk[i] <= n) {
Insert(rt[i], rt[i - 1], 1, n, h[rk[i]]);
}
}
while (q -- ) {
int v, x, k;
cin >> v >> x >> k;
for (int i = 19; i >= 0; -- i) {
if (f[v][i] && val[f[v][i]] <= x) {
v = f[v][i];
}
}
if (siz[v] < k) {
cout << -1 << '\n';
} else {
cout << vec[Query(rt[ed[v]], rt[dfn[v] - 1], 1, n, k) - 1] << '\n';
}
}
return 0;
}
|
题目描述
给定一张$n$个点，$m$条边的无向图，每条边有两个属性：$l$长度、$a$海拔。
我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。
$q$次询问，每次给出起点$v$和当天的水位线$p$，终点默认为$1$，每天都给你一辆车，你可以骑车先经过一些没有积水的路，直到遇到有积水的路，这时你就不能使用车了，接下来的所有的路都必须靠你步行，求从起点到终点步行的最短距离。
思路
首先预处理$1$到$n-1$个节点的最短路，然后按照海拔由高到低排序，建立 $Kruskal$ 重构树，倍增地找海拔$> p$的最浅的节点，若找到则说明你可以骑车到达该子树里任意一个叶子结点，然后步行到终点。若没找到，说明你只能步行，没有骑车的机会，最后维护一下每颗子树内，叶子结点到终点的最短路。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 4e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;
struct Edge {
int u, v, w;
bool operator < (const Edge &o) const {
return w > o.w;
}
};
vector< Edge > g;
struct Node {
LL v, w;
bool operator < (const Node &o) const {
return w > o.w;
}
};
vector< Node > adj[N];
LL dis[N];
bool vis[N];
void dijkstra(int n) {
for (int i = 1; i <= n * 2 - 1; ++ i) {
dis[i] = 1e18;
vis[i] = false;
}
priority_queue< Node > q;
q.push({1, dis[1] = 0});
while (!q.empty()) {
Node p = q.top();
q.pop();
if (vis[p.v]) {
continue;
}
vis[p.v] = true;
for (const auto &[v, w] : adj[p.v]) {
if (!vis[v] && dis[v] > dis[p.v] + w) {
q.push({v, dis[v] = dis[p.v] + w});
}
}
}
}
int f[N][20], val[N];
vector< int > ver[N];
int find(int x) {
return f[x][0] == x ? x : f[x][0] = find(f[x][0]);
}
void dfs(int x, int p) {
f[x][0] = p;
for (int i = 1; i <= 19; ++ i) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (const auto &y : ver[x]) {
if (y ^ p) {
dfs(y, x);
dis[x] = min(dis[x], dis[y]);
}
}
}
void solve() {
int n, m, q, k, s;
cin >> n >> m;
g.clear();
for (int i = 1; i <= n; ++ i) {
adj[i].clear();
}
while (m -- ) {
int u, v, l, a;
cin >> u >> v >> l >> a;
adj[u].push_back({v, l});
adj[v].push_back({u, l});
g.push_back({u, v, a});
}
sort(begin(g), end(g));
for (int i = 1; i <= n * 2 - 1; ++ i) {
f[i][0] = i;
ver[i].clear();
}
int cnt = n;
for (const auto &[u, v, w] : g) {
int fx = find(u), fy = find(v);
if (fx != fy) {
++ cnt;
f[fx][0] = f[fy][0] = cnt;
val[cnt] = w;
ver[cnt] = {fx, fy};
}
}
dijkstra(n);
dfs(cnt, 0);
cin >> q >> k >> s;
int lastans = 0;
while (q -- ) {
int v, p;
cin >> v >> p;
v = (v + k * lastans - 1) % n + 1;
p = (p + k * lastans) % (s + 1);
for (int i = 19; i >= 0; -- i) {
if (f[v][i] && val[f[v][i]] > p) {
v = f[v][i];
}
}
cout << (lastans = dis[v]) << '\n';
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
|
现在回想起来真是太痛了，去年啥都不懂去打区域赛，结果这一站太卷了，一道没听过的$Kruskal$重构树居然过了快$200$个队，为什么人人都会重构树啊！
题目描述
给出一棵具有 $n$ 个点的树，在每个结点处都可以获得$a_i$个硬币，同时每条边具有限制$w_i$，必须拥有不少于 $w_i$ 个硬币才可以通过这条边，共有$q$组询问，每次询问给出起点$s$和初始硬币数$t$，求最终能获得多少硬币。
思路
首先我们按照边权限制从小到大排序，依次建立重构树的边。我们若想获得某颗子树内所有的硬币，那么我们手里的硬币至少要不小于子树根节点的权值，理由如下：我们每枚举一条边可以将两个不同的连通块连接起来时，这条边就是这两个连通块的最小瓶颈边，即只要手中的硬币数不小于这个点的权值，我们就可以从一个连通块走到另一个连通块并且收获另一个连通块的硬币数。所以现在我们可以枚举起点$s$的祖先，因为硬币数和限制时同时变化的，所以我们必须一个一个地跳，但是这样复杂度是 $\Theta(depth_s)$ 的，所以我们从另一个角度想，将限制减去子树内的总硬币数，然后我们倍增地维护节点 $x$ 到 $fa_{x,i}$ 的最大值，当我们手中的硬币数不小于这个最大值时即可将 $x$ 转移到 $fa_{x,i}$。
最后答案即为初始硬币数$+$当前节点子树内叶子结点的硬币数之和。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, q, a[N];
struct Edge {
int u, v, w;
bool operator < (const Edge &o) const {
return w < o.w;
}
};
int f[N][20], val[N], mx[N][20];
vector< int > adj[N];
int find(int x) {
return f[x][0] == x ? x : f[x][0] = find(f[x][0]);
}
void dfs(int x, int p) {
f[x][0] = p;
for (int i = 1; i <= 19; ++ i) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
mx[x][0] = val[p] - a[x];
for (int i = 1; i <= 19; ++ i) {
mx[x][i] = max(mx[x][i - 1], mx[f[x][i - 1]][i - 1]);
}
for (const auto &y : adj[x]) {
if (y ^ p) {
dfs(y, x);
}
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
}
vector< Edge > g;
for (int i = 1; i <= m; ++ i) {
int u, v, w;
cin >> u >> v >> w;
g.push_back({u, v, w});
}
sort(begin(g), end(g));
for (int i = 1; i <= n * 2 - 1; ++ i) {
f[i][0] = i;
}
int cnt = n;
for (const auto &[u, v, w] : g) {
int fx = find(u), fy = find(v);
if (fx != fy) {
++ cnt;
f[fx][0] = f[fy][0] = cnt;
adj[cnt] = {fx, fy};
a[cnt] = a[fx] + a[fy];
val[cnt] = w;
}
}
dfs(cnt, 0);
while (q -- ) {
int x, q;
cin >> x >> q;
for (int i = 19; i >= 0; -- i) {
if (f[x][i] && mx[x][i] <= q) {
x = f[x][i];
}
}
cout << a[x] + q << '\n';
}
return 0;
}
|
$Kruskal$ 重构树变形题，确实很妙，是个质量很好的题目。
题目描述
给出 $n$ 个点，$m$ 条边的不带权连通无向图，$q$ 次询问至少要加完编号前多少的边，才能使得 $[l,r]$ 中的所有点两两连通。
思路
其实初看很难将题目和 $Kruskal$ 重构树结合在一起，现在细想一下，重构树某子树内所有叶子结点之间路径最大边权的最小值其实就是子树根节点的权值。因为原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = $Kruskal$ 重构树上两点之间的 $LCA$ 的权值，拓展到$k$个点之间的所有简单路径上最大边权的最小值其实就是 $Kruskal$ 重构树中这$k$个点的$lca$的权值。简单点说，树上多个点的$LCA$，就是 $DFS$ 序最小的和 $DFS$ 序最大的这两个点的 $LCA$。具体证明请看：如何在 DAG 中找多个点的 LCA ? 其实画个图就是最简单直接的方法。
现在我们考虑建立 $Kruskal$ 重构树，边权为边的编号，现在重构树某子树内所有叶子结点之间能够两两联通的加的边数最大的最小值其实就是整颗子树根节点的权值。
然后我们查询$[l,r]$内所有节点的$LCA$，等价于查询$[l,r]$内$DFS$序最小的点和$DFS$序最大的点的$LCA$，所以我们随便拿一个数据结构来维护区间$DFS$序最小和最大分别对应的节点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, q;
struct UnionFind {
vector< int > f, siz;
UnionFind(int n) : f(n), siz(n, 1) {
iota(begin(f), end(f), 0);
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
f[y] = x;
}
return false;
}
int operator [](int x) { return find(x);}
};
int cnt, idx[N];
vector< int > adj[N];
int dep[N], f[N][20], lg[N], dfn[N];
void dfs(int x) {
if (x <= n) {
dfn[x] = ++ dfn[0];
}
for (int i = 1; i <= lg[n]; ++ i) f[x][i] = f[f[x][i - 1]][i - 1];
for (auto &y : adj[x]) {
dep[y] = dep[x] + 1;
f[y][0] = x;
dfs(y);
}
}
int LCA(int x, int y) {
if (dep[x] > dep[y]) {
swap(x, y);
}
for (int i = lg[n * 2 - 1]; i >= 0; -- i) {
if (dep[f[y][i]] >= dep[x]) {
y = f[y][i];
}
}
if(x == y) {
return x;
}
for (int i = lg[n * 2 - 1]; i >= 0; -- i) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
struct Sparse_Table {
vector< vector< int > > mn, mx;
Sparse_Table(int n) : mn(n + 1, vector< int > (lg[n] + 1, 0)), mx(mn){}
void Build(int n) {
for (int i = 1; i <= n; ++ i) {
mn[i][0] = mx[i][0] = i;
}
for (int j = 1; j <= lg[n]; ++ j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++ i) {
mn[i][j] = dfn[mn[i][j - 1]] > dfn[mn[i + (1 << (j - 1))][j - 1]] ? mn[i + (1 << (j - 1))][j - 1] : mn[i][j - 1];
mx[i][j] = dfn[mx[i][j - 1]] < dfn[mx[i + (1 << (j - 1))][j - 1]] ? mx[i + (1 << (j - 1))][j - 1] : mx[i][j - 1];
}
}
}
pair< int, int > query(int l, int r) {
int k = lg[r - l + 1];
int Max = dfn[mx[l][k]] > dfn[mx[r - (1 << k) + 1][k]] ? mx[l][k] : mx[r - (1 << k) + 1][k];
int Min = dfn[mn[l][k]] < dfn[mn[r - (1 << k) + 1][k]] ? mn[l][k] : mn[r - (1 << k) + 1][k];
return {Max, Min};
}
};
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n * 2 - 1; ++ i) {
adj[i].clear();
dep[i] = dfn[i] = idx[i] = 0;
for (int j = 0; j <= lg[n * 2 - 1]; ++ j) f[i][j] = 0;
}
UnionFind dsu(n * 2);
cnt = n;
for (int i = 1; i <= m; ++ i) {
int u, v;
cin >> u >> v;
u = dsu[u];
v = dsu[v];
if (u != v) {
adj[++ cnt] = {u, v};
idx[cnt] = i;
dsu.f[u] = dsu.f[v] = cnt;
}
}
dfs(cnt);
Sparse_Table st(n);
st.Build(n);
for (int i = 1; i <= q; ++ i) {
int l, r;
cin >> l >> r;
auto [x, y] = st.query(l, r);
cout << idx[LCA(x, y)] << " \n"[i == q];
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
for (int i = 2; i < N; ++ i) {
lg[i] = lg[i >> 1] + 1;
}
int t;
cin >> t;
while (t -- ) solve();
return 0;
}
|
