Heavy-Light Decomposition (HLD)

Heavy-Light Decomposition (HLD) — phân tách nặng nhẹ — là kỹ thuật phân rã một cây có $N$ đỉnh thành các chain (chuỗi đỉnh nối tiếp nhau) sao cho mọi đường đi từ gốc xuống một đỉnh bất kỳ chỉ cắt qua $O(\log N)$ chain. Nhờ vậy, một truy vấn/cập nhật trên đường đi $u\to v$ (tổng, max, min, gán đoạn...) — vốn không có cấu trúc tuyến tính — được quy về $O(\log N)$ truy vấn đoạn liên tiếp trên một mảng, mỗi truy vấn xử lý bằng Segment Tree trong $O(\log N)$. Tổng chi phí mỗi thao tác là $O({\log }^{2}N)$, thay vì $O(N)$ nếu duyệt thẳng đường đi.

HLD áp dụng cho cây cố định về hình dạng (không thêm/xoá cạnh). Nếu cây thay đổi cấu trúc thì cần Link-Cut Tree.

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

Mấu chốt là phân loại cạnh cha–con. Với mỗi đỉnh $u$, gọi $\text{sz}[u]$ là kích thước cây con gốc $u$. Trong các con của $u$, ta chọn con nặng (heavy child) là con có cây con lớn nhất; cạnh nối $u$ tới con nặng gọi là cạnh nặng (heavy edge), mọi cạnh còn lại là cạnh nhẹ (light edge).

Tính chất then chốt: khi đi từ một đỉnh xuống một đỉnh con qua một cạnh nhẹ, kích thước cây con giảm ít nhất một nửa.

Vì sao? Nếu cạnh $u\to v$ là cạnh nhẹ thì $v$ không phải con nặng, nghĩa là tồn tại con nặng $h$ với $\text{sz}[h]\ge \text{sz}[v]$. Suy ra $\text{sz}[u]\ge \text{sz}[v]+\text{sz}[h]\ge 2\text{sz}[v]$, tức $\text{sz}[v]\le \text{sz}[u]/2$. Mỗi lần đi qua một cạnh nhẹ, kích thước cây con bị chia đôi, mà kích thước không thể giảm dưới 1, nên trên đường đi gốc → lá có nhiều nhất ${\log }_{2}N$ cạnh nhẹ, tức nhiều nhất $O(\log N)$ chain khác nhau.

Các cạnh nặng liên tiếp ghép lại thành các heavy chain (đường đi dọc, mỗi chain là một "xương sống"). Bí quyết cài đặt: khi DFS gán chỉ số (đánh số pos), ta luôn đi xuống con nặng trước. Khi đó toàn bộ một chain nhận các chỉ số liên tiếp trên mảng. Một đoạn đường đi nằm trong cùng một chain trở thành một đoạn liên tiếp $[\text{pos}[\text{head}],\text{pos}[u]]$ — đúng thứ mà Segment Tree xử lý nhanh.

Để trả lời truy vấn đường đi $u\to v$, ta cho hai đỉnh "leo" lên gốc: ở mỗi bước, đỉnh nào có đầu chain (head) sâu hơn sẽ nuốt trọn đoạn từ head xuống chính nó (một truy vấn đoạn), rồi nhảy lên đỉnh cha của head — sang chain mới. Lặp đến khi $u,v$ cùng một chain thì truy vấn đoạn cuối giữa chúng. Vì chỉ có $O(\log N)$ chain trên đường đi nên có $O(\log N)$ truy vấn đoạn.

Ví dụ chạy tay

Xét cây 9 đỉnh, gốc 1 (lấy theo ví dụ điển hình):

            1
          / | \
         2  3  4
        /|     |
       5 6      7
      /|
     8 9

Bước 1 — DFS tính sz và chọn con nặng. (con nặng được tô bằng *)

sz[8]=1  sz[9]=1
sz[5]=3  (con: 8,9 -> chọn 8*, hoà thì lấy con đầu)
sz[6]=1
sz[2]=5  (con: 5,6 -> 5* vì sz=3>1)
sz[3]=1
sz[7]=1
sz[4]=2  (con: 7 -> 7*)
sz[1]=9  (con: 2,3,4 -> 2* vì sz=5 lớn nhất)

Cạnh nặng: 1–2, 2–5, 5–8, 4–7. Mọi cạnh khác là cạnh nhẹ.

Bước 2 — decompose: đi con nặng trước, đánh số pos liên tiếp, gán head. Bắt đầu từ gốc 1, chain mới mở khi gặp cạnh nhẹ.

thứ tự thăm :  1   2   5   8   9   6   3   4   7
pos         :  1   2   3   4   5   6   7   8   9
head        :  1   1   1   1   9   6   3   4   4
chain       : [-------- A --------][9][6][3][--B--]

Các chain thu được:

A: 1 - 2 - 5 - 8     (head = 1, pos 1..4)   <- heavy chain dài nhất
   9 đơn lẻ          (head = 9, pos 5)
   6 đơn lẻ          (head = 6, pos 6)
   3 đơn lẻ          (head = 3, pos 7)
B: 4 - 7             (head = 4, pos 8..9)

Bước 3 — truy vấn đường đi, ví dụ tổng giá trị trên $9\to 7$.

Đường đi thật là $9\to 5\to 2\to 1\to 4\to 7$. Ta leo bằng head:

u=9 (head 9, dep head=4)   v=7 (head 4, dep head=2)
  head[9] sâu hơn -> truy vấn đoạn [pos[9],pos[9]] = [5,5]  (đỉnh 9)
  nhảy u = par[head[9]] = par[9] = 5

u=5 (head 1, dep head=1)   v=7 (head 4, dep head=2)
  head[7] sâu hơn -> truy vấn đoạn [pos[4],pos[7]] = [8,9]  (đỉnh 4,7)
  nhảy v = par[head[7]] = par[4] = 1

u=5 (head 1)               v=1 (head 1)   -> cùng chain
  truy vấn đoạn [pos[1],pos[5]] = [1,3]  (đỉnh 1,2,5)

Tổng = (đỉnh 9) + (đỉnh 4,7) + (đỉnh 1,2,5) = đúng tập đỉnh $\{9,5,2,1,4,7\}$. Chỉ 3 truy vấn đoạn cho một đường đi 6 đỉnh — và con số này luôn $\le O(\log N)$ dù cây sâu thế nào.

Cài đặt

Bản dưới đây hỗ trợ: cập nhật giá trị một đỉnh và truy vấn tổng trên đường đi. Đổi phép cộng trong Segment Tree sang max/min để được biến thể tương ứng.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;

int n;
vector<int> adj[MAXN];
int par[MAXN], dep[MAXN], sz[MAXN], heavy[MAXN];
int head_[MAXN], pos_[MAXN], cur_pos;   // head_, pos_ để tránh trùng tên thư viện
long long val[MAXN];                    // giá trị ban đầu tại mỗi đỉnh

// --- Segment Tree (point update, range sum) trên mảng kích thước n ---
long long seg[4 * MAXN];
void seg_update(int node, int l, int r, int p, long long v) {
    if (l == r) { seg[node] = v; return; }
    int mid = (l + r) / 2;
    if (p <= mid) seg_update(2*node,   l,   mid, p, v);
    else          seg_update(2*node+1, mid+1, r, p, v);
    seg[node] = seg[2*node] + seg[2*node+1];
}
long long seg_query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;            // đổi 0 -> -INF nếu dùng max
    if (ql <= l && r <= qr) return seg[node];
    int mid = (l + r) / 2;
    return seg_query(2*node, l, mid, ql, qr)
         + seg_query(2*node+1, mid+1, r, ql, qr);
}

// Bước 1: tính kích thước cây con (sz) và xác định con nặng (heavy)
//  - dùng DFS lặp/đệ quy đều được; ở đây đệ quy cho rõ
int dfs_sz(int u, int p, int d) {
    par[u] = p; dep[u] = d; sz[u] = 1; heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        sz[u] += dfs_sz(v, u, d + 1);
        if (sz[v] > max_sz) { max_sz = sz[v]; heavy[u] = v; } // con nặng nhất
    }
    return sz[u];
}

// Bước 2: gán head và pos. ĐI CON NẶNG TRƯỚC để mỗi chain có pos liên tiếp.
void decompose(int u, int h) {
    head_[u] = h;
    pos_[u]  = ++cur_pos;                     // đánh số 1..n theo thứ tự chain
    if (heavy[u] != -1)
        decompose(heavy[u], h);              // tiếp tục chain hiện tại
    for (int v : adj[u])
        if (v != par[u] && v != heavy[u])
            decompose(v, v);                 // mỗi con nhẹ mở một chain MỚI (head = v)
}

void build(int root) {
    cur_pos = 0;
    dfs_sz(root, 0, 0);
    decompose(root, root);
    for (int i = 1; i <= n; i++)
        seg_update(1, 1, n, pos_[i], val[i]); // nạp giá trị vào đúng vị trí pos
}

// Truy vấn tổng trên đường đi u -> v (giá trị đặt trên ĐỈNH)
long long path_query(int u, int v) {
    long long res = 0;
    while (head_[u] != head_[v]) {           // còn ở hai chain khác nhau
        if (dep[head_[u]] < dep[head_[v]]) swap(u, v); // u có head sâu hơn
        res += seg_query(1, 1, n, pos_[head_[u]], pos_[u]); // nuốt cả đoạn chain
        u = par[head_[u]];                   // nhảy lên chain cha
    }
    // u, v cùng chain: đoạn liên tiếp [min pos, max pos]
    if (dep[u] > dep[v]) swap(u, v);
    res += seg_query(1, 1, n, pos_[u], pos_[v]); // gồm cả đỉnh LCA = u
    return res;
}

// Cập nhật giá trị đỉnh u thành x
void point_update(int u, long long x) {
    seg_update(1, 1, n, pos_[u], x);
}

int main() {
    int q; scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &val[i]);
    for (int i = 0; i < n - 1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    build(1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) { int s; long long x; scanf("%d %lld", &s, &x); point_update(s, x); }
        else         { int a, b; scanf("%d %d", &a, &b); printf("%lld\n", path_query(a, b)); }
    }
    return 0;
}

HLD trên cạnh (trọng số đặt trên cạnh)

Khi trọng số nằm trên cạnh, gán trọng số cạnh $(u,\text{par}[u])$ vào đỉnh con $u$. Khi truy vấn đường đi, phải bỏ qua đỉnh LCA (nó không ứng với cạnh nào trên đường đi):

long long path_query_edge(int u, int v) {
    long long res = 0;
    while (head_[u] != head_[v]) {
        if (dep[head_[u]] < dep[head_[v]]) swap(u, v);
        res += seg_query(1, 1, n, pos_[head_[u]], pos_[u]);
        u = par[head_[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);          // u là LCA
    if (u != v)
        res += seg_query(1, 1, n, pos_[u] + 1, pos_[v]); // +1: bỏ qua đỉnh LCA
    return res;
}

Độ phức tạp

Bộ nhớ: $O(N)$ cho các mảng par, dep, sz, heavy, head_, pos_, val cộng $O(4N)$ cho Segment Tree, tổng $O(N)$. Danh sách kề adj cũng $O(N)$ vì cây có $N-1$ cạnh.

Lưu ý: ${\log }^{2}N$ đến từ việc lồng hai tầng — số chain ($\log N$) nhân chi phí mỗi truy vấn đoạn ($\log N$). Nếu thay Segment Tree bằng Euler tour + Fenwick cho riêng truy vấn gốc→đỉnh thì có thể về $O(\log N)$, nhưng truy vấn đường đi tổng quát vẫn là $O({\log }^{2}N)$ với HLD chuẩn.

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

• Tràn số (overflow). Với truy vấn tổng, giá trị tối đa $\le {10}^9$ và $N\le 2·{10}^5$ cho tổng đường đi tới $~2·{10}^{14}$ — vượt int. Phải dùng long long cho cả mảng giá trị lẫn mảng Segment Tree. Triệu chứng: kết quả âm hoặc sai trên test lớn, AC trên test nhỏ.
• Quên đi con nặng trước trong decompose. Nếu DFS con nhẹ trước thì các đỉnh trong cùng chain không còn liên tiếp trên mảng pos, mọi truy vấn đoạn sai bét. Triệu chứng: đúng trên cây dạng đường thẳng nhưng sai trên cây phân nhánh.
• Phần tử trung tính sai khi đổi sang max/min. Khi chuyển từ tổng sang max, phải đổi giá trị trả về của nhánh "ngoài đoạn" trong seg_query từ 0 thành LLONG_MIN (hoặc một giá trị đủ nhỏ), và phép gộp thành max. Quên việc này khiến đáp án max bị kẹp về 0 khi mọi giá trị âm.
• Sai biên ở HLD trên cạnh: không bỏ đỉnh LCA. Với trọng số cạnh, dùng path_query (đỉnh) sẽ cộng dư giá trị tại LCA. Phải dùng pos_[u]+1 và xử lý riêng trường hợp $u=v$ (đường đi rỗng, kết quả 0), nếu không sẽ truy vấn đoạn [pos_[u]+1, pos_[v]] với l > r gây kết quả rác.
• Đệ quy DFS tràn stack. Với cây dạng "xích" ($N=2·{10}^5$, sâu $2·{10}^5$), dfs_sz đệ quy có thể stack overflow (RTE/MLE). Cách tránh: tăng giới hạn stack, hoặc viết DFS dạng lặp (iterative) cho cả dfs_sz và decompose.
• Quên swap đúng đỉnh khi cùng chain. Sau vòng while, nếu dep[u] > dep[v] mà không swap, truy vấn [pos_[u], pos_[v]] cho l > r. Luôn đảm bảo pos_[u] <= pos_[v] (đỉnh nông hơn có pos nhỏ hơn trong cùng chain).

Biến thể / Mở rộng

• Lazy propagation: thay Segment Tree thường bằng Segment Tree có lazy để hỗ trợ cập nhật đoạn trên đường đi (cộng/gán cả đường đi $u\to v$), vẫn $O({\log }^{2}N)$ mỗi thao tác.
• Truy vấn cây con: nếu cần truy vấn/cập nhật trên cả cây con (subtree), không cần HLD — chỉ cần Euler tour: cây con gốc $u$ chiếm đoạn liên tiếp $[\text{tin}[u],\text{tout}[u]]$. HLD và Euler tour thường được phối hợp.
• LCA bằng HLD: chính vòng leo head trong path_query cho ta LCA "miễn phí" — đỉnh nông nhất gặp ở pha cuối chính là LCA, tính trong $O(\log N)$.
• Xem thêm: Segment Tree, Fenwick Tree.

Bài tập luyện

• Tổ tiên chung thấp nhất - LCA (compqry2) — (Advanced) Tìm LCA của hai đỉnh; chính là cơ chế "leo head" của HLD, bài nhập môn để nắm pha nhảy chain.
• Truy vấn khoảng cách (distqry) — (Advanced) Khoảng cách $=\text{dep}[u]+\text{dep}[v]-2\text{dep}[\text{lca}]$; luyện kết hợp độ sâu với leo chain để ra đáp số đường đi.
• Truy vấn đường đi từ gốc (pathqry) — (Advanced) Tổng giá trị đường gốc → đỉnh kèm cập nhật điểm; bản HLD thu gọn (mọi truy vấn cùng đầu là gốc), bước đệm trước path tổng quát.
• Truy vấn đường đi II (pathqry2) — (Veteran) Max trên đường đi $u\to v$ + cập nhật điểm — bài chuẩn mực của HLD, đúng khuôn code ở trên với phép gộp đổi sang max.
• Đếm đường đi qua đỉnh (cntpath) — (Advanced) Với mỗi đường đi cộng 1 lên mọi đỉnh của nó, rồi đếm; luyện cập nhật đoạn trên đường đi (HLD + lazy, hoặc difference-on-tree) — một ứng dụng khác của khung HLD.
• Phá Mã - Gold (codebreak) — (Veteran) Bài khó phối hợp cây với Segment Tree; rèn khả năng đưa truy vấn cây phức tạp về đoạn liên tiếp như tinh thần HLD.