Wiki › Cấu trúc dữ liệu › Cây › Link-Cut Tree

Link-Cut Tree

huunguyen Updated Tháng sáu 2, 2026

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) thay đổi động, hỗ trợ:

link(u, v) — thêm một cạnh, nối hai cây rời nhau,
cut(u, v) — xóa một cạnh, tách một cây làm đôi,
truy vấn / cập nhật trên cả đường đi $u \to v$ (tổng, min, max, gán, cộng dồn...),

tất cả trong $O (\log N)$ amortized mỗi thao tác. So với cách ngây thơ (mỗi truy vấn duyệt đường đi mất $O (N)$ , mỗi lần đổi cạnh phải dựng lại cấu trúc), LCT đưa toàn bộ về $O ((N + Q) \log N)$ . Đây là công cụ mạnh nhất cho lớp bài "cây/rừng thay đổi cấu trúc theo thời gian", mà Heavy-Light Decomposition hay Binary Lifting — vốn yêu cầu cây tĩnh — không xử lý được.

Ý tưởng / Trực giác

Vấn đề cốt lõi: làm sao đại diện một cây tùy ý sao cho mỗi "đường đi gốc → đỉnh" có thể được gom lại và truy vấn nhanh, kể cả khi cấu trúc cây liên tục đổi?

LCT trả lời bằng phân rã đường đi ưu tiên (Preferred Path Decomposition). Tại mỗi thời điểm ta tô màu cây bằng hai loại cạnh:

Cạnh ưu tiên (preferred / solid): các cạnh này gộp đỉnh thành những đường đi dọc (mỗi đỉnh có nhiều nhất một con ưu tiên). Mỗi đường đi ưu tiên được lưu trong một Splay Tree riêng, sắp theo độ sâu: đỉnh nông nhất nằm bên trái, sâu nhất bên phải. Nhờ thứ tự này, "tổng/min/max trên đoạn đường" chính là thông tin tổng hợp của cả Splay Tree đó.
Cạnh không ưu tiên (dashed): nối giữa các Splay Tree khác nhau. Ta không lưu nó như con thật, mà bằng con trỏ path_parent: gốc của một Splay Tree trỏ lên đỉnh cha (ở cây thật) thuộc đường đi ưu tiên phía trên. Đây là điểm tinh tế — cha trong cây thật không phải lúc nào cũng là cha trong Splay Tree.

Thao tác nền tảng là access(u): nó biến đổi rừng sao cho đường đi từ gốc của cây xuống u trở thành đúng một đường đi ưu tiên duy nhất, và u nằm cuối (sâu nhất). Sau access(u), toàn bộ đường gốc→u nằm gọn trong một Splay Tree, ta splay u lên gốc Splay Tree và đọc thông tin tổng hợp là xong.

Tại sao access rẻ ( $O (\log N)$ amortized)? Mỗi lần access "ngắt" một số cạnh ưu tiên cũ và "tạo" một số cạnh ưu tiên mới. Phân tích thế năng (heavy-light theo kiểu ưu tiên) chứng minh: tổng số lần đổi cạnh ưu tiên qua mọi thao tác là $O ((N + Q) \log N)$ , mỗi lần kèm một thao tác splay $O (\log N)$ amortized. Hai tầng amortized này nhân lại vẫn cho $O (\log N)$ trung bình mỗi thao tác.

Hai mảnh ghép quan trọng còn lại:

make_root(u) — đổi gốc cây chứa u thành chính u. Cần khi muốn truy vấn đường đi tùy ý $u \to v$ (không bắt buộc theo quan hệ tổ tiên): cứ make_root(u) rồi access(v). Để đảo gốc trong $O (\log N)$ , ta dùng lazy reverse: sau access(u), đường gốc cũ→u nằm trong một Splay Tree theo thứ tự độ sâu; đảo gốc thành u chính là đảo ngược thứ tự đường đó, làm bằng cờ rev (lazy flip) y như lazy của Segment Tree.
Vì có lazy rev, trước khi truy cập con của một đỉnh trong splay, phải push_down để đẩy cờ đảo xuống — nếu quên, mọi thứ hỏng âm thầm.

Ví dụ chạy tay

Cây ban đầu (gốc 1), giá trị mỗi đỉnh ghi trong ngoặc, ta sẽ tính tổng trên đường đi $4 \to 5$ :

            1(10)
           /     \
        2(20)    3(30)
        /   \
     4(40)  5(50)

Đường thật $4 \to 5$ đi qua: 4 - 2 - 5, tổng kỳ vọng $= 40 + 20 + 50 = 110$ .

Bước 1 — make_root(4). Ta gọi access(4) rồi flip(4). Sau access(4), đường gốc→4 là 1 - 2 - 4 được gom thành một đường ưu tiên (Splay Tree theo độ sâu, nông→sâu là 1,2,4). Cạnh 2-5 và 1-3 thành dashed (lưu bằng path_parent):

Đường ưu tiên (theo độ sâu):  1 -> 2 -> 4      (nông .... sâu)
dashed (path_parent):  5 --> 2 ,  3 --> 1

flip(4) đảo thứ tự đường này: bây giờ 4 là gốc, độ sâu mới 4 -> 2 -> 1. (Cờ rev được đặt lazy, chưa thực sự lật con cho tới khi push_down.)

Bước 2 — access(5). Ta đi từ 5 ngược lên gốc mới (là 4), nối lại các cạnh ưu tiên:

splay(5): đưa 5 lên gốc Splay Tree của nó. 5 có path_parent trỏ tới 2.
splay(2), đặt con phải của 2 là 5 (nối đường ưu tiên ... -> 2 -> 5), bỏ con phải cũ của 2 (là 4) ra thành dashed.
tiếp tục cho tới khi cả đường 4 -> 2 -> 5 thành một đường ưu tiên duy nhất.

Trạng thái cây Splay sau access(5) (sắp theo độ sâu so với gốc 4): 4(40) -> 2(20) -> 5(50). Cây Splay cụ thể sau khi splay(5) lên gốc:

          5(50)         sum tại nút = tổng cây con
         /
       2(20)
      /
    4(40)

sum[4]=40
sum[2]=40+20=60
sum[5]=60+50=110   <-- đọc ở gốc Splay Tree

Bước 3 — đọc kết quả. Gốc Splay Tree (đỉnh 5) giữ sum = 110. Đúng bằng tổng đường $4 \to 5$ ta tính tay. Mọi thao tác chỉ chạm $O (\log N)$ đỉnh.

Bảng tóm tắt biến đổi đường ưu tiên:

Bước	Thao tác	Đường ưu tiên chứa đích	sum đọc được
0	(ban đầu, gốc 1)	—	—
1	`make_root(4)`	`4 -> 2 -> 1` (đã đảo)	—
2	`access(5)`	`4 -> 2 -> 5`	110

Cài đặt

Cài đặt dùng mảng tĩnh (nhanh hơn con trỏ), chỉ số 0 là nút NULL canh biên. Mỗi đỉnh giữ val (giá trị riêng) và sum (tổng cây con Splay), cùng cờ lazy rev.

const int MAXN = 2e5 + 5;

struct Node {
    int ch[2], par;     // con trái/phải và cha trong Splay Tree
    long long val, sum; // val: giá trị đỉnh; sum: tổng cây con Splay
    bool rev;           // lazy: đảo ngược đoạn đường (dùng cho make_root)
} t[MAXN];

// u có phải gốc của Splay Tree hiện tại không?
// Gốc Splay Tree là đỉnh mà cha của nó KHÔNG nhận nó làm con thật
// (cạnh đó là dashed / path_parent).
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) { // gộp thông tin: trái + bản thân + phải
    t[u].sum = t[t[u].ch[0]].sum + t[u].val + t[t[u].ch[1]].sum;
}

void flip(int u) {                // đặt lazy đảo cho u
    swap(t[u].ch[0], t[u].ch[1]);
    t[u].rev ^= 1;
}

void push_down(int u) {           // đẩy lazy đảo xuống 2 con
    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;
    }
}

// Trước khi splay(u): phải push_down từ gốc Splay Tree XUỐNG tới u,
// vì lazy nằm ở trên đường từ gốc tới u.
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);    // u là con phải của p?
    // Chỉ nối g->u nếu p KHÔNG phải gốc Splay (giữ nguyên path_parent)
    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);       // cập nhật từ dưới lên: p trước, u sau
}

void splay(int u) {
    push_all(u);                  // đẩy hết lazy trên đường tới u
    while (!is_root(u)) {
        int p = t[u].par, g = t[p].par;
        if (!is_root(p))          // zig-zig / zig-zag
            rotate((t[g].ch[0] == p) == (t[p].ch[0] == u) ? p : u);
        rotate(u);
    }
    push_up(u);
}

// access(u): biến đường gốc-thật -> u thành MỘT đường ưu tiên,
// u nằm sâu nhất. Đây là thao tác nền của mọi thao tác khác.
void access(int u) {
    int last = 0;
    for (int v = u; v; v = t[v].par) {
        splay(v);
        t[v].ch[1] = last;        // nối phần đường phía dưới (sâu hơn)
        push_up(v);
        last = v;
    }
    splay(u);
}

// Đổi gốc cây chứa u thành u: access rồi đảo cả đường (lazy rev).
void make_root(int u) {
    access(u);
    flip(u);
}

// Tìm gốc thật của cây chứa u: sau access, đỉnh nông nhất
// là con trái cùng của Splay Tree.
int find_root(int u) {
    access(u);
    while (t[u].ch[0]) { push_down(u); u = t[u].ch[0]; }
    splay(u);                     // splay lại để giữ amortized
    return u;
}

// Nối u-v: chỉ hợp lệ khi u, v thuộc hai cây khác nhau.
void link(int u, int v) {
    make_root(u);
    if (find_root(v) != u)        // đảm bảo không tạo chu trình
        t[u].par = v;             // đặt path_parent của u là v
}

// Cắt cạnh (u, v): chỉ hợp lệ khi cạnh đó thực sự tồn tại.
void cut(int u, int v) {
    make_root(u);
    access(v);
    // Sau make_root(u)+access(v): nếu (u,v) là cạnh thì u là con trái
    // trực tiếp của v trong Splay Tree và u không có con phải.
    if (t[v].ch[0] == u && t[u].ch[1] == 0) {
        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;              // gốc Splay Tree giữ tổng cả đường
}

// Cập nhật giá trị một đỉnh.
void update(int u, long long x) {
    splay(u);                     // splay để u thành gốc, sum đúng sau push_up
    t[u].val = x;
    push_up(u);
}

void init(int n, vector<long long>& a) {
    t[0] = {{0,0}, 0, 0, 0, false}; // nút NULL: sum = 0 (phần tử trung hò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 = false;
    }
}

Khung 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;
        if (op == 0) { cin >> u >> v; link(u, v); }
        else if (op == 1) { cin >> u >> v; cut(u, v); }
        else if (op == 2) { cin >> u >> v; cout << query(u, v) << "\n"; }
        else { cin >> u >> v; update(u, (long long)v); }
    }
}

Độ phức tạp

Thao tác	Thời gian	Vì sao
`access(u)`	$O (\log N)$ amortized	Số cạnh ưu tiên bị đổi qua toàn bộ tiến trình là $O ((N + Q) \log N)$ (phân tích thế năng); mỗi lần kèm một splay $O (\log N)$ amortized
`splay(u)`	$O (\log N)$ amortized	Tính chất chuẩn của Splay Tree
`link`, `cut`, `make_root`, `find_root`, `query`, `update`	$O (\log N)$ amortized	Đều chỉ gọi $O (1)$ lần `access`/`splay`

Tổng thời gian: với $N$ đỉnh và $Q$ thao tác là $O ((N + Q) \log N)$ amortized.
Bộ nhớ: $O (N)$ — mỗi đỉnh giữ số trường cố định (ch[2], par, val, sum, rev). Không cần cấp phát động nếu dùng mảng tĩnh.
Lưu ý: hằng số của LCT lớn hơn HLD/Binary Lifting (hai tầng amortized, nhiều splay). Nếu cây tĩnh, dùng HLD/Binary Lifting thường nhanh hơn nhiều lần. LCT chỉ thắng khi cấu trúc thay đổi động.

⚠️ Lỗi thường gặp

Quên push_down trước khi đi xuống con. Khi có lazy rev (do make_root), nếu duyệt con trong find_root hay trong splay mà chưa đẩy cờ đảo, cây trả về con trật hoàn toàn. Triệu chứng: kết quả sai ngẫu nhiên, sai nhiều hơn khi có nhiều make_root. Cách tránh: luôn push_all(u) đầu mỗi splay, và push_down(u) trước mỗi lần u = t[u].ch[...].
Nhầm cha Splay với cha cây thật trong rotate. Trong rotate, chỉ được nối g -> u khi p không là gốc Splay Tree (!is_root(p)); nếu p là gốc Splay thì cạnh p -> g là dashed (path_parent), phải giữ nguyên t[u].par = g mà không sửa con của g. Sai chỗ này làm con trỏ path_parent biến mất, rừng vỡ. Triệu chứng: vòng lặp trong access/find_root không kết thúc hoặc truy cập sai cây.
link/cut không kiểm tra hợp lệ. link(u, v) khi u, v đã cùng cây sẽ tạo chu trình (LCT chỉ đúng trên rừng) — phải find_root(v) != find_root(u) mới nối. cut(u, v) khi cạnh không tồn tại mà vẫn xóa con sẽ phá cấu trúc. Luôn kiểm tra điều kiện như trong code (t[v].ch[0] == u && t[u].ch[1] == 0).
Tràn số khi cộng đường. Tổng trên đường có thể tới $N$ giá trị $~ 10^{9}$ , vượt int ( $\approx 2.1 \times 10^{9}$ ). Dùng long long cho val, sum và biến đọc kết quả. Triệu chứng: AC test nhỏ, WA test lớn với số âm/quay vòng.
Sai phần tử trung hòa của nút NULL (chỉ số 0). push_up cộng sum của con; nút 0 phải có sum = 0 (với tổng) hoặc $- \infty$ / $+ \infty$ (với max/min). Quên khởi tạo t[0] đúng làm rò "rác" vào kết quả. Với min/max nhớ đặt phần tử trung hòa tương ứng (LLONG_MIN/LLONG_MAX).
Truy vấn đường tùy ý mà quên make_root. access(v) một mình chỉ gom đường gốc hiện tại → v, không phải $u \to v$ . Muốn đường $u \to v$ bất kỳ phải make_root(u) trước rồi access(v). Quên bước này cho kết quả của một đường khác.

Biến thể / Mở rộng

Giá trị trên cạnh thay vì trên đỉnh: tạo một "đỉnh ảo" cho mỗi cạnh giữ giá trị cạnh, hoặc dồn giá trị cạnh vào đỉnh con; khi truy vấn đường $u \to v$ nhớ loại trừ đầu mút. Đây là cách giải bài cập nhật/đọc trên cạnh (xem grassplnt bên dưới).
Lazy cộng dồn / gán trên cả đường: thêm cờ lazy add/assign bên cạnh rev, push_down đồng thời. Cho phép "cộng x cho mọi cạnh trên đường $u \to v$ " trong $O (\log N)$ .
Truy vấn cây con động (subtree query): cần thêm thông tin "virtual subtree" tổng hợp qua các cạnh dashed — biến thể nâng cao hơn, dùng cho rừng động có truy vấn cây con.
Liên hệ: nếu cây tĩnh, ưu tiên Heavy-Light Decomposition (kết hợp Segment Tree) hoặc Binary Lifting cho LCA — đơn giản và nhanh hơn.

Bài tập luyện

Truy vấn đường đi từ gốc (pathqry) — (Advanced) Tổng giá trị đỉnh trên đường gốc→đỉnh kèm cập nhật điểm: làm quen access + đọc tổng tại gốc Splay Tree.
Truy vấn đường đi II (pathqry2) — (Veteran) Max trên đường đi giữa hai đỉnh bất kỳ + cập nhật điểm: luyện make_root + thay phép gộp tổng bằng max (đổi phần tử trung hòa).
Trồng Cỏ Trên Cây (grassplnt) — (Veteran) Cộng 1 cho mọi cạnh trên đường $u \to v$ rồi đọc giá trị một cạnh: bài kinh điển về giá trị trên cạnh + lazy cộng dồn trên đường của LCT.
Cây Đũa Phép Cơm Nguội (elderwand) — (Expert) LCT thuần: link, cut, truy vấn tổng trên đường, cập nhật điểm trên rừng thay đổi động — bài tổng hợp đầy đủ mọi thao tác.