Link-Cut Tree (LCT) là cấu trúc dữ liệu duy trì một rừng các cây có gốc (rooted forest), hỗ trợ các thao tác thay đổi cấu trúc cây và truy vấn trên đường đi — tất cả trong amortized.
Ứng dụng:
- Thêm/xóa cạnh trong rừng động
- Truy vấn tổng, min, max trên đường đi
- Tìm gốc, tìm LCA trong cây thay đổi động
Ý tưởng
LCT dùng kỹ thuật Preferred Path Decomposition: phân rã mỗi cây thành các đường đi (chain). Mỗi chain được lưu trong một Splay Tree theo thứ tự độ sâu từ trên xuống.
Hai loại cạnh:
- Preferred edge (solid): cạnh được chọn, nằm trong cùng một Splay Tree
- Non-preferred edge (dashed): cạnh giữa các Splay Tree khác nhau, lưu qua con trỏ
path_parent
Thao tác access(u) làm cho đường đi từ u lên gốc trở thành một chain duy nhất — đây là thao tác cơ sở của mọi thao tác khác.
Cài đặt
const int MAXN = 2e5 + 5;
struct Node {
int ch[2], par;
long long val, sum;
bool rev; // lazy flip
} t[MAXN];
// Kiểm tra u có phải gốc của Splay Tree không
bool is_root(int u) {
int p = t[u].par;
return t[p].ch[0] != u && t[p].ch[1] != u;
}
void push_up(int u) {
t[u].sum = t[t[u].ch[0]].sum + t[u].val + t[t[u].ch[1]].sum;
}
void flip(int u) {
swap(t[u].ch[0], t[u].ch[1]);
t[u].rev ^= 1;
}
void push_down(int u) {
if (t[u].rev) {
if (t[u].ch[0]) flip(t[u].ch[0]);
if (t[u].ch[1]) flip(t[u].ch[1]);
t[u].rev = 0;
}
}
void push_all(int u) {
if (!is_root(u)) push_all(t[u].par);
push_down(u);
}
void rotate(int u) {
int p = t[u].par, g = t[p].par;
int k = (t[p].ch[1] == u);
if (!is_root(p)) t[g].ch[t[g].ch[1] == p] = u;
t[u].par = g;
t[p].ch[k] = t[u].ch[!k]; if (t[u].ch[!k]) t[t[u].ch[!k]].par = p;
t[u].ch[!k] = p; t[p].par = u;
push_up(p); push_up(u);
}
void splay(int u) {
push_all(u);
while (!is_root(u)) {
int p = t[u].par, g = t[p].par;
if (!is_root(p))
rotate((t[g].ch[0] == p) == (t[p].ch[0] == u) ? p : u);
rotate(u);
}
push_up(u);
}
// Kéo u lên làm root của preferred path từ u đến root cây
void access(int u) {
int last = 0;
for (int v = u; v; v = t[v].par) {
splay(v);
t[v].ch[1] = last;
push_up(v);
last = v;
}
splay(u);
}
// Đổi gốc cây chứa u thành u
void make_root(int u) {
access(u);
flip(u);
}
// Tìm gốc của cây chứa u
int find_root(int u) {
access(u);
while (t[u].ch[0]) { push_down(u); u = t[u].ch[0]; }
splay(u);
return u;
}
// Nối u và v (u và v phải thuộc hai cây khác nhau)
void link(int u, int v) {
make_root(u);
if (find_root(v) != u) {
t[u].par = v;
}
}
// Cắt cạnh (u, v)
void cut(int u, int v) {
make_root(u);
access(v);
// Sau access(v), u là con trái trực tiếp của v trong Splay Tree
if (t[v].ch[0] == u && !t[u].ch[1]) {
t[v].ch[0] = 0;
t[u].par = 0;
push_up(v);
}
}
// Truy vấn tổng trên đường đi u → v
long long query(int u, int v) {
make_root(u);
access(v);
return t[v].sum;
}
Khởi tạo
void init(int n, vector<long long>& a) {
for (int i = 1; i <= n; i++) {
t[i].val = t[i].sum = a[i];
t[i].ch[0] = t[i].ch[1] = t[i].par = 0;
t[i].rev = 0;
}
}
Ví dụ sử dụng
int main() {
int n, q;
cin >> n >> q;
vector<long long> a(n+1);
for (int i = 1; i <= n; i++) cin >> a[i];
init(n, a);
while (q--) {
int op, u, v;
cin >> op >> u >> v;
if (op == 0) { // link u-v
link(u, v);
} else if (op == 1) { // cut u-v
cut(u, v);
} else if (op == 2) { // query sum on path u-v
cout << query(u, v) << "\n";
}
}
}
Độ phức tạp
| Thao tác | Độ phức tạp |
|---|---|
link(u, v) |
amortized |
cut(u, v) |
amortized |
query(u, v) |
amortized |
find_root(u) |
amortized |
make_root(u) |
amortized |
Khi nào dùng LCT?
- Cây thay đổi động (thêm/xóa cạnh)
- Truy vấn trên đường đi trong rừng thay đổi
- Bài toán cần tìm LCA hoặc gốc sau khi cấu trúc cây thay đổi
Nếu cây không thay đổi, dùng Binary Lifting hoặc HLD — đơn giản hơn và hằng số nhỏ hơn.
Bài tập minh họa
- Elder Wand — link, cut, path sum query, point update
Bình luận