前提知識
Kruskal最小/最大全域木アルゴリズム、ダブリング（Binary Lifting）の知識を前提とします。
Kruskal再構築木を構築すると、最小全域木上の2点間のパスの最大重み、および重み ≤ w の辺のみを通って到達可能な点の集合を O(log N) で求めることができます。
近年の競技プログラミングでは出題頻度は控えめですが、該当する問題に遭遇した際に非常に強力なツールとなります。
代表的な問題として、NOIP2013 トラック輸送（Truck Transportation）、NOI2018 帰還（Return）があります。本稿で解説します。
構築方法 (Build)
ここでは、Kruskalアルゴリズムは最小全域木を求めるものであるとします。
通常のKruskal法では、辺を重みの昇順にソートし、両端点が非連結（同じUnion-Find Setに属さない）であればその辺を追加し、Union-Findを統合します。
再構築木の構築では、新たな仮想ノード tot を作成し、そのノードの重みを追加する辺の重みに設定します。そして、統合する2つの集合のルートを、この仮想ノードの左右の子とします。その後、両方の集合と仮想ノードを統合し（仮想ノードをUnion-Findのルートとする）、辺を張ります。
例えば、以下の無向グラフを考えます。
（画像は省略）
対応するKruskal再構築木は以下のようになります。
（画像は省略）
コード実装例は以下の通りです。
void build_kruskal_tree() {
dsu.init(); // Union-Findの初期化
sort(edges.begin(), edges.end()); // 辺のソート
int cur_node = n; // 仮想ノードのID開始値
for (auto &e : edges) {
int ru = dsu.find(e.u), rv = dsu.find(e.v), w = e.w;
if (ru == rv) continue;
val[++cur_node] = w; // 仮想ノードに重みを設定
dsu.merge(ru, cur_node); // ruとcur_nodeを統合
dsu.merge(rv, cur_node); // rvとcur_nodeを統合
tree[cur_node].push_back(ru);
tree[cur_node].push_back(rv);
}
}
性質
- 再構築木は、n個の葉ノードを持つ完全二分木（の形になることが多い）で、葉ノードは全て元の最小全域木上の頂点に対応します。内部ノードは全て仮想ノードです。
- 再構築木のノード重みは最大ヒープの性質を持ちます。
- 元のグラフにおいて、2点u,v間のすべての単純パスにおける辺重みの最大値の最小値は、再構築木上のLCAの重みと等しい。
- 頂点uから、パス上の辺重みの最大値の最小値がk以下となる全ての頂点vは、再構築木上の特定のある部分木内に存在し、かつその部分木内の全ての葉ノードが条件を満たす。
最後の2つの性質が最も頻繁に使用されます。
例題
[NOIP2013 高級組] トラック輸送
出典：リンク
問題文
国Aにはn個の都市（1からn）と、m本の双方向道路があります。各道路には重量制限（最大積載量）があります。q台のトラックが輸送を行います。各トラックは、重量制限を超えない範囲で、最大どれだけの重量の貨物を運べるかを答えてください。
解法
双方向の辺があり、n個の頂点を連結にするにはn-1本の辺があれば十分（木になる）です。可能な限り重い貨物を運ぶには、大きい重みの辺から優先的に選ぶ、つまり最大全域木を構築すれば良いです。
証明：最大全域木に含まれない辺は、より重みの大きい（または等しい）辺で迂回できるためです。
最大全域木を求めた後、各クエリ(u, v)に対して、uからvへのパス上の最小の重みを求めればよいです。これは木上のパス最小値問題であり、 Heavy-Light Decomposition (HLD) や、Kruskal再構築木を用いたLCAで解くことができます。
Kruskal再構築木を構築し、LCAの重み（仮想ノードの重み）を答えます。
参考コード
// ... (コード部分は元のコードから大幅に変更)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int LOG = 20;
int n, m, q;
vector<array<int, 2>> g[MAXN * 2];
int val[MAXN * 2], up[MAXN * 2][LOG], depth[MAXN * 2];
int tot;
struct Edge {
int u, v, w;
bool operator<(const Edge &o) const {
return w > o.w; // 最大全域木のために大きい順
}
};
vector<Edge> edges;
struct DSU {
int fa[MAXN * 2];
void init() { for (int i = 1; i <= n * 2; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
} dsu;
void dfs(int u, int p) {
up[u][0] = p;
depth[u] = depth[p] + 1;
for (int i = 1; i < LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
for (auto &v : g[u]) {
if (v[0] == p) continue;
dfs(v[0], u);
}
}
int get_lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int i = 0; i < LOG; i++) if (diff >> i & 1) u = up[u][i];
if (u == v) return u;
for (int i = LOG - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
void build_kruskal() {
sort(edges.begin(), edges.end());
dsu.init();
tot = n;
for (auto &e : edges) {
int ru = dsu.find(e.u), rv = dsu.find(e.v);
if (ru == rv) continue;
val[++tot] = e.w;
dsu.merge(ru, tot);
dsu.merge(rv, tot);
g[tot].push_back({ru, tot});
g[tot].push_back({rv, tot});
}
// 森になる可能性があるため、全ての根からDFS
for (int i = tot; i >= 1; i--) {
if (!depth[i]) dfs(i, 0);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
edges.push_back({u, v, w});
}
build_kruskal();
cin >> q;
while (q--) {
int u, v; cin >> u >> v;
int lca = get_lca(u, v);
if (lca == 0) cout << -1 << "\n"; // 非連結
else cout << val[lca] << "\n";
}
return 0;
}
[NOI2018] 帰還 (Return)
出典：リンク
問題文
無向グラフが与えられます。各辺には2つのパラメータ l（長さ）と a（標高）があります。q回のクエリがあり、各クエリは (v, p) で与えられます。これは、出発点がvであり、標高がp以下の辺は無料で走行できないことを意味します。また、無料走行は連続している間だけ可能であり、一度でも有料の辺（標高 ≤ p の辺）を使うと、その後全ての辺が有料になります。目的地は頂点1です。各クエリについて、vから1への最小コスト（lの合計）を求めてください。
解法
まず、通常のDijkstra法で、全ての頂点から頂点1への最短距離を計算しておきます。
重要なのは、「無料で走れる辺だけを使って到達できる範囲」を高速に求めることです。無料で走れる条件は、辺の標高 a > p です。a > p である辺のみを通過してvから到達可能な頂点の集合は、Kruskal再構築木を用いて表現できます。
辺を標高の降順にソートしてKruskal再構築木を構築します。このとき、再構築木の内部ノードの重みは、その時点で追加された辺の標高になります。
クエリ (v, p) が来たとき、vから再構築木を上へと辿り、重みが > p である最も高い（根に近い）先祖ノードを見つけます。この先祖ノードが表す部分木内の葉ノードが、vから標高 > p の辺のみで到達可能な頂点の集合です。
後は、その部分木内の頂点の中で、Dijkstraで求めた最短距離が最小のものを答えれば良いです。これは、再構築木上でDFSを行い、各部分木の最短距離の最小値を葉から根に向かって伝播させておく（DP）ことで、効率的に求まります。
参考コード
// ... (コード部分)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MAXN = 400005;
const int LOG = 20;
int n, m;
vector<pair<int, ll>> graph[MAXN];
ll dist[MAXN];
bool vis[MAXN];
struct Edge {
int u, v, a;
bool operator<(const Edge &o) const { return a > o.a; }
};
vector<Edge> edges;
int val[MAXN * 2];
vector<int> tree[MAXN * 2];
int up[MAXN * 2][LOG];
ll subtree_min[MAXN * 2];
int tot;
struct DSU {
int fa[MAXN * 2];
void init() { for (int i = 1; i <= 2 * n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
} dsu;
void dijkstra(int s) {
fill(dist, dist + MAXN, INF);
fill(vis, vis + MAXN, false);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &[v, w] : graph[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
void dfs(int u, int p) {
up[u][0] = p;
subtree_min[u] = (u <= n) ? dist[u] : INF;
for (int i = 1; i < LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
for (int v : tree[u]) {
if (v == p) continue;
dfs(v, u);
subtree_min[u] = min(subtree_min[u], subtree_min[v]);
}
}
void build_kruskal() {
sort(edges.begin(), edges.end());
dsu.init();
tot = n;
for (auto &e : edges) {
int ru = dsu.find(e.u), rv = dsu.find(e.v);
if (ru == rv) continue;
val[++tot] = e.a;
dsu.merge(ru, tot);
dsu.merge(rv, tot);
tree[tot].push_back(ru);
tree[tot].push_back(rv);
}
dfs(tot, 0);
}
int query(int v, int p) {
int u = v;
for (int i = LOG - 1; i >= 0; i--) {
if (up[u][i] != 0 && val[up[u][i]] > p) {
u = up[u][i];
}
}
return u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) {
cin >> n >> m;
// 初期化
for (int i = 1; i <= n; i++) graph[i].clear();
for (int i = 1; i <= 2 * n; i++) tree[i].clear();
edges.clear();
memset(val, 0, sizeof(val));
memset(up, 0, sizeof(up));
for (int i = 0; i < m; i++) {
int u, v, l, a; cin >> u >> v >> l >> a;
graph[u].push_back({v, l});
graph[v].push_back({u, l});
edges.push_back({u, v, a});
}
dijkstra(1);
build_kruskal();
int q, k, s; cin >> q >> k >> s;
int lastans = 0;
while (q--) {
int v0, p0; cin >> v0 >> p0;
int v = (v0 + k * lastans - 1) % n + 1;
int p = (p0 + k * lastans) % (s + 1);
int node = query(v, p);
cout << subtree_min[node] << "\n";
lastans = subtree_min[node];
}
}
return 0;
}
P9638 「yyOI R1」youyou の軍事訓練
出典：リンク
問題文
q個の操作があります。
1 x: 重みがx未満の辺を切断し、以前の操作で切断した辺は元に戻す（履歴はリセットされる）。2 x: 頂点xが属する連結成分のサイズ（頂点数）を答える。3 x y: 番号xの辺の重みをyに変更する。変更後も辺の重みの相対的な大小関係は変わらないことが保証される。
解法
操作1により、クエリ時点で通行可能な辺は、「重みが現在の閾値 lim 以上である辺」のみであると解釈できます。
辺を重みの降順にソートしてKruskal再構築木を構築します。このとき、内部ノード (i) の重み val[i] は、そのノードが表す部分木内の辺の中で最小の重み（すなわち、そのノードを追加した時の辺の重み）となります。
頂点xが、重みが lim 以上の辺のみを使って到達できる頂点の集合は、以下のように求められます。
- xから再構築木を根に向かって上昇し、
val[up[x][k]] >= limを満たす最も高い（根に近い）先祖ノードancを見つける。 - その
ancを根とする部分木に含まれる元の頂点（葉ノード）の個数が、答えとなります。
そのため、DFSで各部分木のサイズ sz を前計算しておきます。
操作3については、辺の相対的な大小関係が変わらないという保証があるため、再構築木の形状は変わりません。よって、単純に該当する内部ノードの重みを更新すればよいです。更新後もヒープ性は保たれます。
参考コード
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 800005;
const int LOG = 20;
int n, m, q;
vector<pair<int, int>> tree[MAXN];
int val[MAXN], up[MAXN][LOG], sz[MAXN];
int tot, lim;
struct Edge {
int u, v, w, id;
bool operator<(const Edge &o) const { return w > o.w; }
};
vector<Edge> edges;
int edge_node[MAXN];
struct DSU {
int fa[MAXN];
void init() { for (int i = 1; i <= 2 * n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
} dsu;
void dfs(int u, int p) {
up[u][0] = p;
sz[u] = (u <= n) ? 1 : 0;
for (int i = 1; i < LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
for (auto &[v, w] : tree[u]) {
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
void build() {
sort(edges.begin(), edges.end());
dsu.init();
tot = n;
for (auto &e : edges) {
int ru = dsu.find(e.u), rv = dsu.find(e.v);
if (ru == rv) continue;
val[++tot] = e.w;
edge_node[e.id] = tot;
dsu.merge(ru, tot);
dsu.merge(rv, tot);
tree[tot].push_back({ru, e.w});
tree[tot].push_back({rv, e.w});
}
// 複数の根があるかもしれないので、根からDFS
for (int i = tot; i >= 1; i--) {
if (up[i][0] == 0) dfs(i, 0);
}
}
int climb(int u) {
for (int i = LOG - 1; i >= 0; i--) {
if (up[u][i] != 0 && val[up[u][i]] >= lim) {
u = up[u][i];
}
}
return u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
edges.push_back({u, v, w, i});
}
build();
while (q--) {
int op; cin >> op;
if (op == 1) {
cin >> lim;
} else if (op == 2) {
int x; cin >> x;
int anc = climb(x);
cout << sz[anc] << "\n";
} else {
int x, y; cin >> x >> y;
val[edge_node[x]] = y;
}
}
return 0;
}