Cây Kruskal (Kruskal Reconstruction Tree)
Cây Kruskal ghi lại quá trình hợp thành phần của thuật toán Kruskal thành một cây 2n-1 nút, biến bài đường đi minimax thành LCA và tập đỉnh đi tới được dưới một ngưỡng thành một cây con (một đoạn lá liên tiếp).
Cây Kruskal (Kruskal Reconstruction Tree, viết tắt KRT) là cây được dựng song song với thuật toán Kruskal: mỗi khi một cạnh trọng số hợp hai thành phần liên thông, ta tạo một nút mới mang giá trị và cho hai nút đại diện của hai thành phần làm con của nó. Kết quả là một cây nhị phân có nút: lá là các đỉnh của đồ thị, nút trong ứng với cạnh của cây khung nhỏ nhất.
Cây này "ghi lại lịch sử" của DSU, và biến các câu hỏi về ngưỡng trọng số thành câu hỏi trên cây:
- Đường đi minimax: trong mọi đường đi từ tới , giá trị nhỏ nhất có thể của cạnh lớn nhất trên đường bằng giá trị của trên cây Kruskal.
- Tập đi tới được dưới ngưỡng: tập đỉnh đi tới được từ chỉ dùng cạnh có trọng số là tập lá của một cây con, tìm được bằng nhảy nhị phân từ lá ; theo thứ tự DFS, tập lá đó là một đoạn liên tiếp, nên mọi cấu trúc dữ liệu trên mảng (sparse table, segment tree, cây phân đoạn bền vững...) dùng được ngay.
Với , dựng cây mất (sắp xếp cạnh) và mỗi truy vấn , trả lời online được, trong khi cách "Kruskal song song với truy vấn" chỉ chạy offline.
Ý tưởng / Trực giác
Dựng cây. Sắp các cạnh theo trọng số tăng dần và chạy Kruskal với DSU. Mỗi thành phần hiện tại được đại diện bởi một nút của cây Kruskal (gốc của cây con chứa đúng các đỉnh của thành phần). Khi cạnh nối hai thành phần khác nhau có nút đại diện và , tạo nút mới với , con là và ; từ nay đại diện cho thành phần hợp. Cạnh nối hai đỉnh cùng thành phần thì bỏ qua, đúng như Kruskal. Lá có giá trị (hoặc ).
Tính chất 1: giá trị tăng dần khi đi lên. Nút được tạo sau có giá trị nút tạo trước (vì cạnh được xét theo thứ tự tăng dần), và cha luôn được tạo sau con. Vậy trên đường từ một lá lên gốc, giá trị không giảm: cây Kruskal là một max-heap theo .
Tính chất 2: thành phần dưới ngưỡng là một cây con. Gọi là đồ thị chỉ giữ các cạnh có trọng số . Khi Kruskal vừa xử lý xong mọi cạnh , các thành phần của DSU chính là các thành phần liên thông của (các cạnh bị bỏ qua không làm thay đổi tính liên thông). Mỗi thành phần đó được đại diện bởi một nút có mà cha (nếu có) có giá trị . Từ lá đi lên, nhờ tính chất 1, nút đó là tổ tiên cao nhất của có : tìm bằng Binary Lifting trong .
Tính chất 3: minimax qua LCA. Đỉnh và liên thông trong khi và chỉ khi tổ tiên cao nhất có của chúng trùng nhau, tức là khi . Giá trị nhỏ nhất thỏa điều kiện chính là : đó là đáp án của bài "đường đi có cạnh lớn nhất nhỏ nhất" (bottleneck path). Đây cũng là cạnh lớn nhất trên đường đi giữa và trong cây khung nhỏ nhất, nhưng cây Kruskal cho thêm tính chất 2, điều mà cây khung không cho trực tiếp.
Tính chất 4: thứ tự lá theo DFS. Duyệt DFS cây Kruskal và đánh số các lá theo thứ tự gặp. Lá của một cây con luôn được đánh số liên tiếp, nên mỗi nút ứng với một đoạn . Kết hợp với tính chất 2: "các đỉnh đi tới được từ qua cạnh " là một đoạn của mảng lá. Ví dụ hỏi giá trị lớn nhất trên các đỉnh đó là bài RMQ trên đoạn; hỏi phần tử nhỏ thứ là bài k-th trên đoạn (cây phân đoạn bền vững hoặc wavelet tree).
Muốn cạnh nhỏ nhất lớn nhất? Xét cạnh theo trọng số giảm dần: cây thành min-heap, giá trị tại LCA là giá trị lớn nhất có thể của cạnh nhỏ nhất trên đường, và "đi được qua các cạnh " thành một cây con.
Ví dụ chạy tay
Đồ thị 5 đỉnh, 6 cạnh (viết theo dạng ):
2 3 1 4 5 2 2 1 3
1 3 4 3 4 5 2 5 6
Sắp tăng dần theo rồi chạy Kruskal (nút mới đánh số từ 6):
| Cạnh | Đại diện hai đầu | Hành động | |
|---|---|---|---|
| 2-3 | 1 | 2, 3 | tạo nút 6 (val 1), con 2 và 3 |
| 4-5 | 2 | 4, 5 | tạo nút 7 (val 2), con 4 và 5 |
| 2-1 | 3 | 6, 1 | tạo nút 8 (val 3), con 6 và 1 |
| 1-3 | 4 | 8, 8 | cùng thành phần: bỏ qua |
| 3-4 | 5 | 8, 7 | tạo nút 9 (val 5), con 8 và 7 |
| 2-5 | 6 | 9, 9 | cùng thành phần: bỏ qua |
Cây Kruskal thu được (trong ngoặc là giá trị, bên dưới là đoạn lá theo thứ tự DFS, đánh số từ 0):
tree root=9 9 8 9 7 8 6 8 1 7 4 7 5 6 2 6 3 label 9 (5) [0,4] label 8 (3) [0,2] label 7 (2) [3,4] label 6 (1) [0,1]
thứ tự lá theo DFS: vị trí 0 1 2 3 4
đỉnh 2 3 1 4 5
Các truy vấn (kết quả in ra từ chính chương trình ở mục Cài đặt và khớp với vét cạn):
| Truy vấn | Cách tính trên cây | Kết quả |
|---|---|---|
| minimax(1, 3) | LCA(1, 3) = 8, val = 3 | 3 (đường 1-2-3 có cạnh lớn nhất 3, tốt hơn cạnh trực tiếp 1-3 nặng 4) |
| minimax(2, 5) | LCA(2, 5) = 9, val = 5 | 5 (đường 2-3-4-5, tốt hơn cạnh trực tiếp nặng 6) |
| minimax(1, 4) | LCA(1, 4) = 9, val = 5 | 5 |
| đi từ 4, cạnh | 4 lên 7 (val 2 4), lên 9 (val 5 > 4): dừng ở 7, đoạn [3, 4] | 2 đỉnh |
| đi từ 1, cạnh | 1 lên 8 (val 3 3), lên 9 (5 > 3): dừng ở 8, đoạn [0, 2] | 3 đỉnh |
| đi từ 2, cạnh | lên tới gốc 9, đoạn [0, 4] | 5 đỉnh |
Chú ý đoạn của nút 8 gồm các đỉnh : thứ tự lá không phải thứ tự chỉ số đỉnh, nên mọi mảng dùng cho truy vấn đoạn phải được xếp lại theo thứ tự lá.
Cài đặt
Chương trình dưới đây dựng cây Kruskal và trả lời hai loại truy vấn online:
1 u v: giá trị nhỏ nhất có thể của cạnh lớn nhất trên một đường đi từ tới (in nếu , nếu không liên thông).2 v x: số đỉnh đi tới được từ chỉ dùng các cạnh có trọng số .
Mẹo cài đặt: nút cha luôn có chỉ số lớn hơn nút con (vì được tạo sau), nên duyệt chỉ số giảm dần là duyệt từ gốc xuống, không cần DFS để tính độ sâu hay bảng nhảy nhị phân. Gốc DSU của một thành phần được đặt luôn là nút cây Kruskal mới tạo, nên find(u) trả về trực tiếp nút đại diện. Đồ thị có thể không liên thông: khi đó ta được một rừng, mỗi gốc tự làm cha của chính nó trong bảng nhảy.
#include <bits/stdc++.h>
using namespace std;
// Cây Kruskal: lá 0..n-1 là đỉnh gốc, nút trong n..tot-1 tạo ra mỗi lần hợp hai thành phần.
// Truy vấn "1 u v": cạnh lớn nhất nhỏ nhất có thể trên đường u -> v (-1 nếu không liên thông).
// Truy vấn "2 v x": số đỉnh đi tới được từ v chỉ dùng cạnh có trọng số <= x.
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<array<long long, 3>> edges(m); // {w, u, v}
for (auto& [w, u, v] : edges) {
cin >> u >> v >> w;
u--, v--;
}
sort(edges.begin(), edges.end()); // xét cạnh theo trọng số tăng dần
int N = 2 * n;
vector<int> dsu(N), par(N, -1), lc(N, -1), rc(N, -1);
vector<long long> val(N, 0); // lá có giá trị 0
iota(dsu.begin(), dsu.end(), 0);
auto find = [&](int x) { // gốc DSU chính là nút cây Kruskal của thành phần
while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]];
return x;
};
int tot = n;
for (auto& [w, u, v] : edges) {
int a = find(u), b = find(v);
if (a == b) continue; // cạnh tạo chu trình: bỏ qua như Kruskal
int id = tot++;
val[id] = w;
lc[id] = a, rc[id] = b;
par[a] = par[b] = id;
dsu[a] = dsu[b] = id; // nút mới làm gốc DSU của thành phần mới
}
// Cha luôn có chỉ số lớn hơn con, nên duyệt chỉ số giảm dần là đi từ gốc xuống.
int LOG = 1;
while ((1 << LOG) < tot) LOG++;
vector<vector<int>> up(LOG, vector<int>(tot));
for (int x = tot - 1; x >= 0; x--) up[0][x] = (par[x] == -1 ? x : par[x]);
for (int k = 1; k < LOG; k++)
for (int x = 0; x < tot; x++) up[k][x] = up[k - 1][up[k - 1][x]];
vector<int> dep(tot, 0);
for (int x = tot - 1; x >= 0; x--)
if (par[x] != -1) dep[x] = dep[par[x]] + 1;
// Thứ tự lá theo DFS: lá của mỗi cây con là một đoạn liên tiếp [L, R].
vector<int> L(tot), R(tot);
int pos = 0;
for (int r = 0; r < tot; r++) {
if (par[r] != -1) continue; // chỉ bắt đầu từ gốc (đồ thị có thể không liên thông)
vector<int> st = {r};
while (!st.empty()) {
int x = st.back();
st.pop_back();
if (x < n) L[x] = R[x] = pos++;
else st.push_back(rc[x]), st.push_back(lc[x]);
}
}
for (int x = n; x < tot; x++) L[x] = min(L[lc[x]], L[rc[x]]), R[x] = max(R[lc[x]], R[rc[x]]);
auto lca = [&](int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int k = LOG - 1; k >= 0; k--)
if (dep[u] - (1 << k) >= dep[v]) u = up[k][u];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--)
if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
return up[0][u];
};
while (q--) {
int t;
cin >> t;
if (t == 1) {
int u, v;
cin >> u >> v;
u--, v--;
if (u == v) cout << 0 << "\n";
else if (find(u) != find(v)) cout << -1 << "\n";
else cout << val[lca(u, v)] << "\n"; // giá trị tại LCA
} else {
int v;
long long x;
cin >> v >> x;
v--;
// nhảy lên tổ tiên cao nhất còn có giá trị <= x (giá trị tăng dần khi đi lên)
for (int k = LOG - 1; k >= 0; k--)
if (val[up[k][v]] <= x) v = up[k][v];
cout << R[v] - L[v] + 1 << "\n"; // số lá trong cây con
}
}
}
import sys
def main():
# Cây Kruskal: lá 0..n-1 là đỉnh gốc, nút trong n..tot-1 tạo ra mỗi lần hợp hai thành phần.
# Truy vấn "1 u v": cạnh lớn nhất nhỏ nhất có thể trên đường u -> v (-1 nếu không liên thông).
# Truy vấn "2 v x": số đỉnh đi tới được từ v chỉ dùng cạnh có trọng số <= x.
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
p = 3
edges = []
for _ in range(m):
u, v, w = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2])
p += 3
edges.append((w, u, v))
edges.sort() # xét cạnh theo trọng số tăng dần
N = 2 * n
dsu = list(range(N))
par = [-1] * N
lc = [-1] * N
rc = [-1] * N
val = [0] * N # lá có giá trị 0
def find(x): # gốc DSU chính là nút cây Kruskal của thành phần
while dsu[x] != x:
dsu[x] = dsu[dsu[x]]
x = dsu[x]
return x
tot = n
for w, u, v in edges:
a, b = find(u), find(v)
if a == b:
continue # cạnh tạo chu trình: bỏ qua như Kruskal
idx = tot
tot += 1
val[idx] = w
lc[idx], rc[idx] = a, b
par[a] = par[b] = idx
dsu[a] = dsu[b] = idx # nút mới làm gốc DSU của thành phần mới
# Cha luôn có chỉ số lớn hơn con, nên duyệt chỉ số giảm dần là đi từ gốc xuống.
LOG = 1
while (1 << LOG) < tot:
LOG += 1
up0 = [x if par[x] == -1 else par[x] for x in range(tot)]
up = [up0]
for _ in range(1, LOG):
prev = up[-1]
up.append([prev[prev[x]] for x in range(tot)])
dep = [0] * tot
for x in range(tot - 1, -1, -1):
if par[x] != -1:
dep[x] = dep[par[x]] + 1
# Thứ tự lá theo DFS: lá của mỗi cây con là một đoạn liên tiếp [L, R].
L = [0] * tot
R = [0] * tot
pos = 0
for r in range(tot):
if par[r] != -1:
continue # chỉ bắt đầu từ gốc (đồ thị có thể không liên thông)
st = [r]
while st:
x = st.pop()
if x < n:
L[x] = R[x] = pos
pos += 1
else:
st.append(rc[x])
st.append(lc[x])
for x in range(n, tot):
L[x] = min(L[lc[x]], L[rc[x]])
R[x] = max(R[lc[x]], R[rc[x]])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
for k in range(LOG - 1, -1, -1):
if dep[u] - (1 << k) >= dep[v]:
u = up[k][u]
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u, v = up[k][u], up[k][v]
return up[0][u]
out = []
for _ in range(q):
t = int(data[p])
if t == 1:
u, v = int(data[p + 1]) - 1, int(data[p + 2]) - 1
if u == v:
out.append(0)
elif find(u) != find(v):
out.append(-1)
else:
out.append(val[lca(u, v)]) # giá trị tại LCA
else:
v, x = int(data[p + 1]) - 1, int(data[p + 2])
# nhảy lên tổ tiên cao nhất còn có giá trị <= x (giá trị tăng dần khi đi lên)
for k in range(LOG - 1, -1, -1):
if val[up[k][v]] <= x:
v = up[k][v]
out.append(R[v] - L[v] + 1) # số lá trong cây con
p += 3
print("\n".join(map(str, out)))
main()
Bản Python chạy khoảng 2 giây cho trên máy thử (C++ khoảng 0,2 giây).
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Sắp xếp cạnh + Kruskal dựng cây | ||
| Bảng nhảy nhị phân, độ sâu, đoạn lá | ||
| Truy vấn minimax (LCA) | ||
| Truy vấn cây con dưới ngưỡng |
Cây có nút và độ sâu có thể tới (ví dụ đồ thị đường thẳng với trọng số tăng dần), nên bảng nhảy cần tầng, với là tầng. Mỗi truy vấn là một lần LCA hoặc một lần nhảy nhị phân, đều . DSU ở đây chỉ dùng nén đường (gốc mới luôn là nút mới), vẫn đủ nhanh trong thực tế.
⚠️ Lỗi thường gặp
- Khai báo mảng cỡ : cây có nút, mọi mảng
par,val,up,dsuphải cỡ . Khai báo cỡ thì ghi tràn ngay khi tạo nút thứ . - Nối nhầm đỉnh gốc thay vì nút đại diện: nút mới phải nhận con là
find(u)vàfind(v)(nút cây Kruskal đại diện cho thành phần), không phải và . Nối thẳng làm một đỉnh có nhiều cha và cây sai hoàn toàn. - Quên sắp xếp cạnh, hoặc sắp sai chiều: tính chất heap (giá trị tăng dần khi đi lên) chỉ đúng khi cạnh được xét theo thứ tự trọng số. Bài hỏi "cạnh nhỏ nhất lớn nhất" hay "chỉ đi qua cạnh " thì phải sắp giảm dần và đổi chiều so sánh khi nhảy.
- Nhảy nhị phân sai điều kiện: khi tìm tổ tiên cao nhất có , điều kiện là
val[up[k][v]] <= xrồi mới nhảy. Nếu viết<thì các cạnh có trọng số đúng bằng bị loại. Với gốc,uptrỏ về chính nó nên nhảy vượt quá gốc vẫn an toàn. - Đồ thị không liên thông: kết quả là một rừng. Truy vấn minimax phải kiểm tra
find(u) == find(v)trước khi lấy LCA, và DFS đánh số lá phải chạy từ mọi gốc. Quên điều này thì LCA của hai cây khác nhau trả về rác. - Dùng thứ tự chỉ số đỉnh thay cho thứ tự lá: đoạn là vị trí trong thứ tự DFS của lá. Muốn hỏi max/k-th trên đoạn đó, phải dựng mảng
a[pos] = giá trị của đỉnh ở vị trí pos, không dùng mảng gốc theo chỉ số đỉnh.
Biến thể / Mở rộng
- Cây Kruskal theo trọng số đỉnh: khi ràng buộc nằm trên đỉnh ("chỉ đi qua các đỉnh có độ cao "), thêm đỉnh theo giá trị tăng dần; khi thêm đỉnh , nút mới (hoặc chính ) làm cha của mọi thành phần kề đã có. Mọi tính chất giữ nguyên, cây không còn nhị phân.
- Kết hợp cấu trúc dữ liệu trên đoạn lá: max/min (sparse table), tổng (tiền tố), phần tử nhỏ thứ (cây phân đoạn bền vững, xem Persistent Segment Tree), đếm điểm trong hình chữ nhật (Fenwick quét offline) đều làm được trên các đoạn .
- Gộp thông tin dọc theo cây: nhiều bài cần cộng một đại lượng trên mọi tổ tiên của lá (ví dụ mỗi nút đóng góp nhân với kích thước cây con anh em). Do cha có chỉ số lớn hơn con, chỉ cần một vòng lặp theo chỉ số giảm dần.
- Liên hệ: cây Kruskal là cách nhìn "theo thời gian" của DSU; khi các cạnh được thêm theo thời gian (thay cho trọng số), giá trị tại LCA là thời điểm sớm nhất hai đỉnh liên thông. Câu hỏi LCA trên cây xem ở trang LCA; thứ tự lá theo DFS là trường hợp riêng của Euler tour. Nếu đồ thị có cả xoá cạnh, xem DSU có hoàn tác.
Bài tập luyện
- Người giao hàng (voi25_ship): (Hard) Quy hoạch động theo vị trí, mỗi bước cần giá trị lớn nhất trên đường đi giữa hai đỉnh của cây; một cách tính là dựng cây Kruskal theo trọng số đỉnh, khi đó giá trị cần tìm nằm ở LCA.
- Nâng cấp cổng (hntst26_e): (Very Hard) Hỏi có đi được từ tới khi được nâng cấp một cổng; thành phần ở ngưỡng là một cây con của cây Kruskal (xét cạnh giảm dần), thứ tự lá biến câu hỏi "có cạnh nối hai thành phần" thành đếm điểm trong hình chữ nhật.
- Hành trình hỗn loạn (icpc24regj): (Expert) Chọn hoán vị để tổng giá trị minimax giữa các cặp liên tiếp lớn nhất; thứ tự lá DFS của cây Kruskal (thăm con nhiều lá hơn trước) làm mọi thành phần dưới ngưỡng thành đoạn liên tiếp, rồi xen kẽ hai nửa.
- Truy Vấn Đường Mới (newroadsq): (Expert) Hỏi ngày đầu tiên hai thành phố liên thông khi đường được xây dần; dựng cây Kruskal theo thứ tự ngày, đáp án là giá trị tại LCA.
Bình luận