Thi đấu

Phân Rã Cây Nặng Nhẹ (Heavy-Light Decomposition - HLD)

Phân rã cây Heavy-Light Decomposition (HLD) là kỹ thuật chia cấu trúc cây thành các chuỗi đường đi nặng rời rạc, cho phép thực hiện các thao tác cập nhật và truy vấn trên đường đi bất kỳ trong thời gian O(log^2 N).

Phân Rã Cây Nặng Nhẹ (Heavy-Light Decomposition - HLD)

Trên một mảng một chiều, chúng ta đã quá quen thuộc với các cấu trúc dữ liệu như Segment Tree (Cây phân đoạn) hay Fenwick Tree (Binary Indexed Tree) giúp cập nhật giá trị và tính tổng hoặc tìm giá trị lớn nhất trên một đoạn con \([L, R]\) trong thời gian \(O(\log N)\).

Thế nhưng, khi bài toán chuyển từ mảng sang một cấu trúc cây (Tree) gồm \(N\) đỉnh:

  • Yêu cầu cập nhật giá trị của một đỉnh hoặc các đỉnh trên đường đi nối giữa hai đỉnh bất kỳ \((u, v)\).
  • Yêu cầu truy vấn tổng trọng số hoặc giá trị lớn nhất trên đường đi giữa \((u, v)\).

Làm sao chúng ta có thể giải quyết các truy vấn này trong thời gian đa thức logarit mà không bị rơi vào thuật toán duyệt DFS/BFS vét cạn \(O(N)\) cho mỗi câu hỏi? Heavy-Light Decomposition (HLD - Phân rã cây nặng nhẹ) chính là chìa khóa vạn năng giải quyết trọn vẹn bài toán này bằng cách biến mọi đường đi trên cây thành tối đa \(O(\log N)\) đoạn liên tiếp trên một cấu trúc Segment Tree 1D!

PHÂN RÃ CÂY NẶNG NHẸ (HEAVY-LIGHT DECOMPOSITION) Biến đường đi bất kỳ trên cây thành O(log N) đoạn liên tiếp trên Segment Tree Cấu trúc cây với Cạnh Nặng (Heavy) & Nhẹ (Light) 1 2 3 4 5 6 7 Heavy Edge Light Edge Trải phẳng chuỗi nặng lên Segment Tree XÍCH NẶNG #1 (head = 1): pos: [1: u=1] [2: u=2] [3: u=4] [4: u=6] XÍCH NẶNG #2 (head = 5): pos: [5: u=5] XÍCH NẶNG #3 (head = 3): pos: [6: u=3] [7: u=7] ✓ Mọi xích nặng là 1 đoạn liên tiếp trên ST TÍNH CHẤT VÀ ĐỘ PHỨC TẠP: Đường đi (u, v) qua ≤ 2 log₂ N xích nặng ⇒ Truy vấn & Cập nhật: O(log² N) • Cây con u: O(log N).
PHÂN RÃ CÂY HLD Heavy-Light Decomposition & Segment Tree 1. Cây và Cạnh Nặng / Nhẹ 1 2 3 4 5 Cạnh Nặng Cạnh Nhẹ 2. Mảng Segment Tree 1D: Xích 1 (head=1): [1, 2, 4] liên tiếp Xích 2 (head=3): [3] | Xích 3: [5] ✓ Bước qua tối đa O(log N) xích nhẹ ĐỘ PHỨC TẠP THUẬT TOÁN: • Truy vấn / Cập nhật đường đi: O(log² N) • Cập nhật / Truy vấn cây con: O(log N)
Phân rã cạnh Nặng - Nhẹ trên cây và kỹ thuật trải phẳng xích nặng lên Segment Tree.

Tư tưởng phân rã cạnh Nặng và cạnh Nhẹ

Xét một cây có gốc gồm \(N\) đỉnh (quy ước gốc là đỉnh \(1\)). Gọi \(\text{sz}[u]\) là kích thước cây con có gốc tại \(u\) (tổng số đỉnh nằm trong nhánh con của \(u\), tính cả \(u\)).

Với mỗi đỉnh cha \(u\) có tập các đỉnh con là \(\{v_1, v_2, \dots, v_k\}\):

  1. Cạnh nặng (Heavy Edge): Là cạnh nối \(u\) tới đỉnh con \(v\) có kích thước cây con \(\text{sz}[v]\) lớn nhất: \[\text{sz}[v] \ge \text{sz}[w] \quad \forall w \in \text{children}(u)\] Nếu có nhiều con có cùng kích thước lớn nhất, ta tùy ý chọn một đỉnh. Do đó, mỗi đỉnh cha chỉ có duy nhất một cạnh nặng đi xuống con (hoặc không có nếu là nút lá).
  2. Cạnh nhẹ (Light Edge): Tất cả các cạnh nối từ \(u\) tới các đỉnh con còn lại được gọi là cạnh nhẹ.

Định lý cốt lõi về số lượng cạnh nhẹ

Khi ta đi từ một đỉnh \(u\) bất kỳ lên gốc cây dọc theo các cạnh nối:

  • Nếu bước qua một cạnh nhẹ \((v \to u)\) với \(u\) là cha của \(v\), thì theo định nghĩa con nặng, kích thước cây con \(\text{sz}[u]\) ít nhất phải gấp đôi kích thước của \(v\): \[\text{sz}[u] \gt 2 \cdot \text{sz}[v]\]
  • Vì kích thước cây tối đa là \(N\), nên trên bất kỳ đường đi nào từ một đỉnh bất kỳ lên gốc, chúng ta chỉ có thể bước qua tối đa \(\lfloor \log_2 N \rfloor\) cạnh nhẹ!

Xích nặng (Heavy Chains / Paths)

Các cạnh nặng liên tiếp nhau tạo thành các chuỗi đường đi có hướng gọi là xích nặng (Heavy Chains). Đỉnh cao nhất của một xích nặng được gọi là đỉnh đầu xích (head). Mỗi đỉnh trên cây thuộc về duy nhất một xích nặng (một đỉnh đơn lẻ không nối cạnh nặng nào cũng được xem là một xích nặng có độ dài 1).

Từ định lý trên, ta suy ra tính chất mang tính cách mạng:

Tính chất đường đi HLD: Đường đi đơn giữa hai đỉnh bất kỳ \((u, v)\) trên cây đi qua tối đa \(2 \log_2 N\) xích nặng!

Trải phẳng cây bằng thứ tự duyệt DFS ưu tiên con nặng

Để biến các xích nặng thành các đoạn liên tiếp trên mảng 1D, chúng ta sử dụng hai lượt duyệt DFS:

Lượt 1: dfs_size(u, p, d)

  • Tính mảng \(\text{depth}[u]\) (độ sâu của đỉnh \(u\)).
  • Tính \(\text{parent}[u]\) (đỉnh cha trực tiếp).
  • Tính \(\text{sz}[u]\) (kích thước cây con).
  • Xác định đỉnh con nặng \(\text{heavy}[u]\).

Lượt 2: dfs_decompose(u, h)

  • Gán \(\text{head}[u] = h\) (đỉnh đầu của xích nặng chứa \(u\)).
  • Đánh số lại đỉnh \(u\) bằng chỉ số mảng tăng dần \(\text{pos}[u] = \mathrm{cur\_pos}{+}{+}\).
  • Quy tắc vàng: Luôn luôn gọi đệ quy duyệt con nặng \(\text{heavy}[u]\) trước tiên, và giữ nguyên đầu xích \(h\): \[\mathrm{dfs\_decompose}(\text{heavy}[u], h)\]
  • Sau khi nhánh con nặng đã được đánh số liên tiếp, mới duyệt qua các đỉnh con nhẹ \(v\), và mỗi con nhẹ này sẽ bắt đầu một xích nặng mới: \[\mathrm{dfs\_decompose}(v, v)\]

Nhờ thứ tự duyệt đặc biệt này:

  1. Mọi đỉnh trên cùng một xích nặng sẽ có chỉ số \(\text{pos}\) liên tiếp nhau! Đoạn từ \(u\) đến \(v\) trên cùng một xích nặng tương ứng với đoạn \([\text{pos}[u], \text{pos}[v]]\) trên mảng.
  2. Toàn bộ cây con của đỉnh \(u\) cũng có chỉ số \(\text{pos}\) nằm liên tiếp nhau trong đoạn \([\text{pos}[u], \text{pos}[u] + \text{sz}[u] - 1]\).

Thuật toán truy vấn và cập nhật trên đường đi

Giả sử cần tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(u\) và \(v\):

  1. Nếu \(u\) và \(v\) không thuộc cùng một xích nặng (\(\text{head}[u] \ne \text{head}[v]\)):
    • Đỉnh nào có đầu xích nằm sâu hơn (độ sâu lớn hơn) sẽ nhảy trước: nếu \(\text{depth}[\text{head}[u]] \gt \text{depth}[\text{head}[v]]\) thì ta hoán vị \(u\) và \(v\), để \(v\) luôn là đỉnh có đầu xích sâu hơn.
    • Truy vấn giá trị trên đoạn từ \(\text{head}[v]\) đến \(v\) trên Segment Tree: đoạn \([\text{pos}[\text{head}[v]], \text{pos}[v]]\).
    • Nhảy \(v\) lên cha của đầu xích: \(v = \text{parent}[\text{head}[v]]\).
  2. Lặp lại bước 1 cho đến khi \(u\) và \(v\) thuộc cùng một xích nặng (\(\text{head}[u] == \text{head}[v]\)):
    • Lúc này \(u\) và \(v\) cùng nằm trên một chuỗi liên tiếp. Giả sử \(u\) nông hơn \(v\) (\(\text{depth}[u] \le \text{depth}[v]\)).
    • Truy vấn nốt đoạn \([\text{pos}[u], \text{pos}[v]]\) trên Segment Tree.
    • Kết thúc và tổng hợp kết quả.

Vì mỗi lần nhảy ta bỏ qua trọn vẹn một xích nặng, và số lần nhảy tối đa là \(2 \log_2 N\), mỗi lần truy vấn Segment Tree tốn \(O(\log N)\), nên tổng thời gian truy vấn đường đi chỉ là:

\[O(\log_2^2 N)\]

Học cùng giảng viên

Chủ đề này nằm trong Buổi 06 - LCA & Tree Query của Tài năng lập trình. Xem đề cương

Cài đặt hoàn chỉnh C++17 và Python 3

Dưới đây là mã nguồn hoàn chỉnh của kỹ thuật Heavy-Light Decomposition kết hợp cây phân đoạn Segment Tree, hỗ trợ cập nhật điểm và truy vấn giá trị lớn nhất trên đường đi:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Cấu trúc Phân rã cây Heavy-Light Decomposition (HLD) kết hợp Segment Tree
// Hỗ trợ cập nhật điểm và truy vấn GTLN trên đường đi cây trong O(log^2 N)
const long long INF = 1e18;

struct HLD {
    int n;
    vector<long long> values;
    vector<vector<int>> adj;
    vector<int> parent, depth, heavy, head, pos;
    vector<long long> tree;
    int cur_pos;

    HLD(int _n, const vector<long long>& init_vals) : n(_n), values(init_vals) {
        adj.assign(n + 1, vector<int>());
        parent.assign(n + 1, 0);
        depth.assign(n + 1, 0);
        heavy.assign(n + 1, 0);
        head.assign(n + 1, 0);
        pos.assign(n + 1, 0);
        tree.assign(4 * n + 4, -INF);
        cur_pos = 1;
    }

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // DFS 1: Tính kích thước cây con, độ sâu, cha và đỉnh con nặng (heavy child)
    int dfs_size(int u, int p, int d) {
        parent[u] = p;
        depth[u] = d;
        int sz = 1;
        int max_c_sz = 0;
        for (int v : adj[u]) {
            if (v != p) {
                int c_sz = dfs_size(v, u, d + 1);
                sz += c_sz;
                if (c_sz > max_c_sz) {
                    max_c_sz = c_sz;
                    heavy[u] = v;
                }
            }
        }
        return sz;
    }

    // DFS 2: Phân rã các xích nặng và đánh số lại đỉnh liên tiếp
    void dfs_decompose(int u, int h) {
        head[u] = h;
        pos[u] = cur_pos++;
        if (heavy[u] != 0) {
            dfs_decompose(heavy[u], h);
        }
        for (int v : adj[u]) {
            if (v != parent[u] && v != heavy[u]) {
                dfs_decompose(v, v);
            }
        }
    }

    void build() {
        dfs_size(1, 0, 0);
        dfs_decompose(1, 1);
        for (int i = 1; i <= n; i++) {
            update_st(1, 1, n, pos[i], values[i]);
        }
    }

    void update_st(int node, int l, int r, int idx, long long val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) update_st(2 * node, l, mid, idx, val);
        else update_st(2 * node + 1, mid + 1, r, idx, val);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }

    long long query_st(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        long long res = -INF;
        if (ql <= mid) res = max(res, query_st(2 * node, l, mid, ql, qr));
        if (qr > mid) res = max(res, query_st(2 * node + 1, mid + 1, r, ql, qr));
        return res;
    }

    void update_node(int u, long long val) {
        values[u] = val;
        update_st(1, 1, n, pos[u], val);
    }

    long long query_path(int u, int v) {
        long long res = -INF;
        while (head[u] != head[v]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            res = max(res, query_st(1, 1, n, pos[head[v]], pos[v]));
            v = parent[head[v]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        res = max(res, query_st(1, 1, n, pos[u], pos[v]));
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> val(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    HLD hld(n, val);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        hld.add_edge(u, v);
    }

    hld.build();

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            long long x;
            cin >> u >> x;
            hld.update_node(u, x);
        } else {
            int u, v;
            cin >> u >> v;
            cout << hld.query_path(u, v) << "\n";
        }
    }

    return 0;
}

Lưu ý: hai hàm DFS trong code viết đệ quy. Với cây suy biến thành đường thẳng, độ sâu đệ quy bằng \(N\): khi \(N\) cỡ \(10^5\) và giới hạn stack là 8 MB, bản C++ có thể bị tràn stack (Runtime Error). Lúc đó hãy viết lại hai hàm DFS bằng ngăn xếp tự quản lý, hoặc tăng giới hạn stack nếu hệ chấm cho phép.

Xử lý các biến thể truy vấn cây nâng cao

  1. Truy vấn trên cây con (Subtree Queries): Một ưu điểm tuyệt đối của cách đánh số DFS tin[u] ưu tiên con nặng là: toàn bộ cây con gốc \(u\) luôn tạo thành một đoạn chỉ số liên tiếp trên mảng trải phẳng: \[[\text{tin}[u], \text{tin}[u] + \text{sz}[u] - 1]\] Do đó, để cập nhật hoặc truy vấn toàn bộ cây con gốc \(u\), ta chỉ cần thực hiện đúng một thao tác Segment Tree duy nhất trong \(O(\log N)\) mà không cần nhảy chuỗi HLD!

  2. Bài toán trọng số nằm trên cạnh (Edge Weights): Trong nhiều đề bài, trọng số được gán cho các cạnh thay vì đỉnh. Để áp dụng HLD:

    • Ta đẩy trọng số của mỗi cạnh \((u, v)\) (với \(u\) là cha của \(v\)) xuống đỉnh con \(v\): \(\text{val}[v] = \text{weight}(u, v)\). Đỉnh gốc không nhận giá trị từ cạnh nào.
    • Khi truy vấn đường đi giữa \(u\) và \(v\), ta tìm \(\text{lca} = \text{LCA}(u, v)\). Đường đi giữa \(u\) và \(v\) bao gồm mọi cạnh ngoại trừ đỉnh \(\text{lca}\).
    • Do đó, khi gom các đoạn Segment Tree trên xích nặng cuối cùng chứa \(\text{lca}\), ta chỉ truy vấn tới \(\text{tin}[\text{lca}] + 1\) thay vì \(\text{tin}[\text{lca}]\).

So sánh HLD với các kỹ thuật truy vấn cây khác

Kỹ thuật Cập nhật đỉnh / cạnh Truy vấn đường đi Truy vấn cây con Bộ nhớ Độ phức tạp cài đặt
Binary Lifting (Nâng nhị phân) \(O(N)\) (khó cập nhật động) \(O(\log N)\) (chỉ truy vấn tĩnh) Không hỗ trợ \(O(N \log N)\) Trung bình
Euler Tour + Fenwick Tree \(O(\log N)\) \(O(\log N)\) (chỉ tính tổng) \(O(\log N)\) \(O(N)\) Dễ
Heavy-Light Decomposition (HLD) \(O(\log N)\) \(O(\log^2 N)\) (mọi phép kết hợp: max/min/sum) \(O(\log N)\) \(O(N)\) Khá dài
Link-Cut Tree (LCT) \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) \(O(N)\) Rất phức tạp (Splay Tree)

Luyện ngay trên Big-O Coding

Để nắm vững kỹ thuật phân rã cây Heavy-Light Decomposition và thuần thục các thao tác truy vấn đường đi, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:

HLD có dùng để tìm tổ tiên chung gần nhất (LCA) được không?

Có, và thậm chí chạy cực kỳ nhanh! Trong quá trình nhảy head, khi hai đỉnh cùng thuộc một xích nặng (\(\text{head}[u] == \text{head}[v]\)), đỉnh nào có độ sâu nhỏ hơn chính là LCA của hai đỉnh ban đầu: \[\text{LCA}(u, v) = (\text{depth}[u] \lt \text{depth}[v]) \ ? \ u : v\] Thuật toán tìm LCA bằng HLD chỉ tốn tối đa \(O(\log N)\) bước nhảy mà không cần bảng nhị phân \(20 \times N\), tiết kiệm đáng kể bộ nhớ cache.

Nếu trọng số nằm trên cạnh thay vì trên đỉnh thì xử lý thế nào?

Quy tắc chuẩn: Ta đẩy trọng số của mỗi cạnh xuống đỉnh con nằm sâu hơn trong hai đầu mút của cạnh đó. Vì trong cây có gốc, mỗi đỉnh (ngoại trừ gốc) có đúng một cạnh nối lên cha của nó. Khi truy vấn đường đi giữa \(u\) và \(v\), ta tìm \(w = \text{LCA}(u, v)\) và chỉ lấy giá trị trên đường đi từ \(u\) tới con của \(w\), cùng từ \(v\) tới con của \(w\), loại trừ chính đỉnh \(w\) (vì trọng số lưu tại \(w\) tương ứng với cạnh nối lên cha của \(w\)).

HLD có thể kết hợp với Fenwick Tree thay cho Segment Tree không?

Hoàn toàn được! Nếu bài toán chỉ yêu cầu tính tổng trên đường đi (Sum query) và cộng dồn điểm, việc thay Segment Tree bằng Fenwick Tree (BIT) sẽ giúp code ngắn hơn một nửa và tốc độ thực thi nhanh hơn khoảng 3 đến 4 lần nhờ hằng số bộ nhớ cache tối ưu.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483