MST Edge Queries
What Happens When You Add One More Edge?
You've built the MST. Now someone hands you a new edge and asks: "Would this improve things?" This is the core question behind MST edge queries. Adding an edge to a tree creates exactly one cycle. If the new edge is lighter than the heaviest edge in that cycle, you can swap them for a better tree.
The Fundamental Technique
Given an MST and a query edge (u, v, w):
- Find the path from u to v in the MST.
- Find the maximum edge weight on that path. Call it
maxW. - Compare: if w < maxW, replacing that max edge with the query edge gives a lighter spanning tree.
This is a direct application of the cycle property. Adding (u, v, w) creates a cycle. If w is less than the max edge in the cycle, that max edge shouldn't be in the MST anymore.
💡 Key insight. The MST path between two nodes is the path that minimizes the maximum edge weight. This is called the minimax path property.
Finding Max Edge on a Tree Path
Brute force: walk from u to v, track the max. This is O(N) per query.
For Q queries, that's O(NQ). Too slow for 2*10^5.
The fix: binary lifting. Preprocess the tree so that for each node u and each power-of-two jump 2^k, you store:
- up[u][k] = the 2^k-th ancestor of u
- mx[u][k] = the max edge weight on the path from u to its 2^k-th ancestor
Query the max on any path using LCA in O(log N).
int up[200005][18], mx[200005][18], dep[200005];
void dfs(int u, int p, int d,
vector<vector<pair<int,int>>>& adj) {
up[u][0] = p;
dep[u] = d;
for (int k = 1; k < 18; k++) {
up[u][k] = up[up[u][k-1]][k-1];
mx[u][k] = max(mx[u][k-1],
mx[up[u][k-1]][k-1]);
}
for (auto [v, w] : adj[u]) {
if (v == p) continue;
mx[v][0] = w;
dfs(v, u, d + 1, adj);
}
}
int queryMax(int u, int v) {
int res = 0;
if (dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
for (int k = 0; k < 18; k++)
if ((diff >> k) & 1) {
res = max(res, mx[u][k]);
u = up[u][k];
}
if (u == v) return res;
for (int k = 17; k >= 0; k--)
if (up[u][k] != up[v][k]) {
res = max({res, mx[u][k], mx[v][k]});
u = up[u][k];
v = up[v][k];
}
return max({res, mx[u][0], mx[v][0]});
}
Problem 1: abc235_e — MST + 1
Problem: Given a weighted graph, build the MST. For each of Q query edges (u, v, w), answer: is there an MST that includes this edge?
Solution:
- Build the MST using Kruskal's.
- Root the MST tree and build binary lifting with max-edge tracking.
- For each query edge (u, v, w): find the max edge on the MST path from u to v. If w <= maxW, the answer is "Yes" (the query edge can replace the max edge, or ties with it).
#include <bits/stdc++.h>
using namespace std;
int par[200005], rnk[200005];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rnk[a] < rnk[b]) swap(a, b);
par[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
}
int up[200005][18], mx[200005][18], dep[200005];
vector<vector<pair<int,int>>> adj;
void dfs(int u, int p, int d) {
up[u][0] = p; dep[u] = d;
for (int k = 1; k < 18; k++) {
up[u][k] = up[up[u][k-1]][k-1];
mx[u][k] = max(mx[u][k-1], mx[up[u][k-1]][k-1]);
}
for (auto [v, w] : adj[u]) {
if (v == p) continue;
mx[v][0] = w;
dfs(v, u, d + 1);
}
}
int queryMax(int u, int v) {
int res = 0;
if (dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
for (int k = 0; k < 18; k++)
if ((diff >> k) & 1) { res = max(res, mx[u][k]); u = up[u][k]; }
if (u == v) return res;
for (int k = 17; k >= 0; k--)
if (up[u][k] != up[v][k]) {
res = max({res, mx[u][k], mx[v][k]});
u = up[u][k]; v = up[v][k];
}
return max({res, mx[u][0], mx[v][0]});
}
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<tuple<int,int,int>> edges(m);
for (auto& [w, u, v] : edges) cin >> u >> v >> w;
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) { par[i] = i; rnk[i] = 0; }
adj.resize(n + 1);
for (auto [w, u, v] : edges) {
if (find(u) != find(v)) {
unite(u, v);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
memset(mx, 0, sizeof(mx));
dfs(1, 0, 0);
while (q--) {
int u, v, w;
cin >> u >> v >> w;
int maxOnPath = queryMax(u, v);
cout << (w <= maxOnPath ? "Yes" : "No") << "\n";
}
}
⚠ Gotcha. The condition is
w <= maxOnPath, notw < maxOnPath. If the query edge ties with the max edge on the path, you can swap them and get an equally valid MST that includes the query edge.
Problem 2: abc218_e — Destruction
Problem: You have N nodes and M weighted edges. You can remove edges for a reward equal to their weight (if positive). Maximize total reward while keeping the graph connected.
Translation: Keep a spanning tree (to stay connected). Remove everything else. To maximize reward, keep the minimum cost spanning tree so that the removed edges have maximum total weight.
#include <bits/stdc++.h>
using namespace std;
int par[200005], rnk[200005];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rnk[a] < rnk[b]) swap(a, b);
par[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
}
int main() {
int n, m;
cin >> n >> m;
vector<tuple<int,int,int>> edges(m);
long long totalPositive = 0;
for (auto& [w, u, v] : edges) {
cin >> u >> v >> w;
if (w > 0) totalPositive += w;
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) { par[i] = i; rnk[i] = 0; }
long long mstCost = 0;
for (auto [w, u, v] : edges) {
if (find(u) != find(v)) {
unite(u, v);
if (w > 0) mstCost += w;
}
}
cout << totalPositive - mstCost << "\n";
}
💡 Key insight. Negative-weight edges are always kept (free to keep, costly to remove). The MST naturally includes them since they're lightest. The reward comes from removing positive-weight non-MST edges.
Problem 3: abc252_e — Road Reduction
Problem: N cities, M roads with costs. Choose exactly N-1 roads to minimize total cost. Output the indices of the chosen roads.
This is literally "find the MST and print which edges you used."
#include <bits/stdc++.h>
using namespace std;
int par[200005], rnk[200005];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rnk[a] < rnk[b]) swap(a, b);
par[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
}
int main() {
int n, m;
cin >> n >> m;
vector<tuple<int,int,int,int>> edges(m); // (w, u, v, idx)
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges[i] = {w, u, v, i + 1};
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) { par[i] = i; rnk[i] = 0; }
vector<int> ans;
for (auto [w, u, v, idx] : edges) {
if (find(u) != find(v)) {
unite(u, v);
ans.push_back(idx);
}
}
for (int i = 0; i < (int)ans.size(); i++)
cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
}
The trick is tracking the original edge index through the sort. Store it as a fourth element in the tuple.
⚠ Gotcha. The problem uses 1-indexed edges. Make sure your index matches the input order, not the sorted order.
Pattern Summary
| Problem Type | Approach |
|---|---|
| "Can this edge be in an MST?" | Build MST, query max on path, compare |
| "Maximize removed edge weight" | Keep MST, remove everything else |
| "Which edges form the MST?" | Kruskal's with index tracking |
| "Does adding edge X improve MST?" | Max on MST path < new edge weight |
Try It
The starter code has DSU ready. For abc235_e, add binary lifting and max-edge queries.
Test case (abc235_e style):
MST edges: (1,2,1), (2,4,2), (2,3,3). Total = 6. Query (1,3,4): max on path 1-2-3 is 3, and 4 > 3, so No. Wait -- re-check. Query (1,3,4): 4 > 3 so this edge can't improve the MST. But can it be in some MST? No, since 4 > 3. Query (1,4,3): max on path 1-2-4 is 2, and 3 > 2, so No.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| abc235_e — MST + 1 | atcoder.jp/contests/abc235/tasks/abc235_e | Medium |
| abc218_e — Destruction | atcoder.jp/contests/abc218/tasks/abc218_e | Medium |
| abc252_e — Road Reduction | atcoder.jp/contests/abc252/tasks/abc252_e | Easy |