Heavy-Light Decomposition: Khi "Nặng" Hóa "Nhẹ"

Nếu anh em thấy hay thì ủng hộ mình 1 follow + 1 upvote + 1 bookmark + 1 comment cho bài viết này tại Mayfest 2025 nhé, cảm ơn anh em!

Hi anh em! Lại là tôi, "thợ code dạo" chuyên "bóc phốt" giải thuật đây! Anh em đã bao giờ "toát mồ hôi hột" khi phải mò mẫm tìm tổng, max, min trên một con đường "dài lê thê" giữa hai cái nút "xa lắc xa lơ" trong một cái cây "siêu to khổng lồ" chưa? Hay "đau đầu hơn" là phải cập nhật giá trị cho cả một "đoạn trường tân thanh" mà chỉ sợ "Time Limit Exceeded" (TLE) nó "vẫy gọi thân thương"? Mấy bài toán trên cây, với cái cấu trúc "rối như canh hẹ", đôi khi đúng là "ác mộng" của anh em coder mình.

Mấy "chiêu" duyệt cây "cổ điển" như DFS, BFS tuy "dễ xài" nhưng lại "đuối sức" khi số truy vấn "đông như quân Nguyên" hoặc cây "dài và ngoằn ngoèo như rắn". Nhưng đừng lo, hôm nay tôi sẽ giới thiệu một "siêu anh hùng" trong làng giải thuật trên cây: Heavy-Light Decomposition, hay gọi thân mật là HLD! "Em nó" như một "kiến trúc sư trưởng" tài ba, "chia để trị" một cách "siêu ngầu", biến những con đường "loằng ngoằng" trên cây thành những "cao tốc" thẳng tắp, "xử lý" trong một nốt nhạc.

Nghe có vẻ "nặng đô" phải không? Yên tâm, với chút "gia vị" hài hước và ví dụ "dễ hiểu như ăn kẹo", anh em sẽ thấy HLD cũng "nhẹ nhàng tình cảm" và "thú vị bất ngờ"!

1. "Bắt Mạch" Cây: Nặng Nhẹ Phân Tranh

Chào anh em, tôi đây! Trước khi "xử lý" cái cây, anh em mình phải làm quen với "dân cư" trong đó đã. Trong thế giới HLD, con cái của một nút cha không phải đứa nào cũng "nặng ký" như nhau đâu nhé!

Để phân loại, chúng ta dùng một cái "cân" đặc biệt: kích thước cây con (subtree size). Nôm na là đếm xem mỗi nhánh có bao nhiêu nút, tính cả gốc nhánh đó.

• "Con Cưng" - Heavy Child (Con Nặng): Trong đám con của một nút, đứa nào có "cân nặng" (subtree size) lớn nhất thì được phong làm "Heavy Child". Đây là đứa "to con" nhất nhà, gánh vác phần lớn "dân số". Một ông bố chỉ có tối đa một "con cưng" thôi nhé. Nếu lỡ có mấy đứa "nặng ký" bằng nhau thì cứ chọn đại một đứa, HLD không khó tính đâu.
• "Con Ghẻ" - Light Child (Con Nhẹ): Những đứa con còn lại, không phải "con cưng", thì là "Light Child". Tụi này "nhẹ cân" hơn, chiếm phần nhỏ trong "gia phả".

Từ đó, ta có các loại "đường xá":

• Cạnh Nặng (Heavy Edge): Đường nối từ cha đến "con cưng" (Heavy Child). Đây là "đại lộ" ưu tiên.
• Cạnh Nhẹ (Light Edge): Đường nối từ cha đến "con ghẻ" (Light Child). Đây là mấy "đường làng", "lối rẽ" nhỏ hơn.

Việc phân biệt "nặng" - "nhẹ" này chính là bí quyết của HLD. Nó giúp chúng ta ưu tiên những nhánh "trọng điểm", đảm bảo khi rẽ vào nhánh "nhẹ", quy mô bài toán sẽ giảm đi đáng kể. Cứ nhớ, đi trên "đại lộ" thì bon bon, rẽ vào "hẻm" là chuẩn bị sang một "khu phố" khác rồi đấy!

Tóm lại một bảng cho dễ hình dung:

Nền tảng của màn "phân loại" này là tính chính xác kích thước cây con. Thông tin này là đầu vào trực tiếp để HLD "quy hoạch" cây thành các chuỗi nặng – trái tim của thuật toán.

2. "Chặt Cây" Kiểu HLD: Đường Rối Cũng Hóa Thẳng Tắp!

Sau khi biết mặt "dân chơi hệ nặng" và "hệ nhẹ", giờ là lúc chúng ta học cách HLD "chặt cây" – hay nói đúng hơn là "phân luồng giao thông" trên cây. Mục tiêu là chia cây ban đầu thành các Chuỗi Nặng (Heavy Paths hoặc Heavy Chains).

Tưởng tượng mỗi chuỗi nặng là một con đường cao tốc, nơi anh em có thể di chuyển một mạch từ đầu đến cuối mà không phải rẽ ngang rẽ dọc nhiều. Đỉnh lá cũng có thể coi là một chuỗi nặng "mini" nếu nó không phải điểm cuối của một cạnh nặng nào.

Thuật Toán "Quy Hoạch" Cây:

Thường thì chúng ta sẽ dùng hai lượt duyệt DFS (Depth First Search – duyệt ưu tiên theo chiều sâu) thần thánh:

• Bước 1: DFS "Đo Dân Số"

  • Lượt DFS này như một cuộc tổng điều tra dân số. Ta sẽ đi từ gốc, tính toán cho mỗi nút u:
    • size[u]: Kích thước cây con gốc u (đã nói ở phần 1).
    • par[u]: Cha trực tiếp của u.
    • depth[u]: Độ sâu của u (khoảng cách từ gốc).
  • Trong lúc duyệt quay lui (post-order traversal), size[u] được tính bằng 1 (cho chính u) cộng với tổng size của tất cả các con của u.
  • Dựa vào size của các con, ta xác định luôn heavyChild[u] – đứa con "nặng ký" nhất của u.

• Bước 2: DFS "Phân Làn Cao Tốc"

  • Lượt DFS thứ hai này sẽ xây dựng các "cao tốc" (chuỗi nặng) và gán thông tin cần thiết cho việc truy vấn sau này.
  • Khi duyệt từ cha u xuống con v:
    • Ưu tiên duyệt Heavy Child trước: Nếu v là heavyChild[u], thì v sẽ thuộc cùng một chuỗi nặng với u.
    • Xử lý Light Child: Nếu v là một Light Child của u, thì v sẽ trở thành đầu của một chuỗi nặng mới (chainHead).
  • Trong lượt DFS này, ta sẽ gán cho mỗi nút u:
    • chainHead[u]: Nút "cao nhất" trong cây của chuỗi nặng mà u thuộc về.
    • pos[u]: Vị trí của nút u trong một mảng "phẳng" (tưởng tượng như số kilomet trên cao tốc). Các nút trên cùng một chuỗi nặng sẽ có pos liên tiếp nhau. Điều này đạt được bằng cách ưu tiên duyệt Heavy Child.

Sau khi HLD "ra tay", cái cây rối rắm ban đầu giờ đã được chia thành các "cao tốc" (chuỗi nặng) và các "lối rẽ" (cạnh nhẹ) nối giữa chúng. Gọn gàng hơn hẳn phải không anh em?

Tính Chất "Thần Kỳ": Tại Sao Chỉ Có $O(\log N)$ Cạnh Nhẹ Trên Đường Đi?

Đây là "ma thuật" của HLD! Khi anh em di chuyển trên cây từ một nút lên cha của nó, nếu cạnh đó là cạnh nhẹ, thì kích thước cây con của nút con (nơi anh em vừa rời đi) sẽ nhỏ hơn một nửa kích thước cây con của nút cha. Nghĩ đơn giản: rẽ vào "đường làng" (cạnh nhẹ) nghĩa là anh em đang đi vào một nhánh cây "ít dân" hơn hẳn so với việc đi vào "đại lộ" (cạnh nặng).

Cứ mỗi lần rẽ vào "đường làng" như vậy trên đường đi từ một nút bất kỳ lên gốc, "quy mô" của khu vực anh em đang xét (đại diện bởi subtree size) gần như tăng lên ít nhất gấp đôi (hoặc ngược lại, subtree size của nút con trên cạnh nhẹ nhỏ hơn một nửa subtree size của nút cha). Vì kích thước cây không thể vượt quá N (tổng số nút), anh em không thể "nhân đôi" quy mô này quá $O(\log N)$ lần.

Do đó, trên bất kỳ đường đi nào từ một nút lên gốc, số lượng cạnh nhẹ anh em phải đi qua không vượt quá $O(\log N)$. Điều này cực kỳ quan trọng! Nó đảm bảo rằng dù đường đi giữa hai nút u và v có dài đến mấy, nó cũng chỉ "nhảy" qua lại giữa các "cao tốc" (chuỗi nặng) tối đa $O(\log N)$ lần thôi. Đây chính là chìa khóa cho độ phức tạp $O(\log^2 N)$ của các truy vấn đường đi mà chúng ta sẽ khám phá ngay sau đây.

3. HLD "Song Kiếm Hợp Bích" Cùng Segment Tree: Cặp Bài Trùng Truy Vấn

HLD đã "quy hoạch" lại cây rất đẹp rồi. Nhưng để thực sự "làm xiếc" với các truy vấn như tính tổng, tìm min/max trên một đường đi, HLD cần một "cạ cứng". Và đó chính là Segment Tree (Cây Phân Đoạn)!

Nếu anh em chưa quen, Segment Tree là một cấu trúc dữ liệu "bá đạo", cho phép thực hiện các truy vấn (ví dụ: tổng, min, max) và cập nhật trên một đoạn của một mảng trong thời gian $O(\log N)$. Chính khả năng xử lý đoạn hiệu quả này khiến Segment Tree trở thành đối tác lý tưởng cho HLD.

Biến "Cao Tốc" Thành Mảng Phẳng:

Nhớ lại ở phần 2, chúng ta đã gán một giá trị pos[u] cho mỗi nút u. Điều kỳ diệu là, các nút trên cùng một chuỗi nặng sẽ có các giá trị pos liên tiếp nhau. Điều này có nghĩa là mỗi "cao tốc" (chuỗi nặng) giờ đây tương ứng với một đoạn thẳng trong một mảng lớn, thường gọi là baseArray. Và khi đã có mảng, Segment Tree có thể "vào việc"!

Giá trị được lưu tại baseArray[pos[u]] sẽ phụ thuộc vào bài toán:

• Nếu truy vấn trên giá trị nút, baseArray[pos[u]] lưu giá trị của nút u.
• Nếu truy vấn trên giá trị cạnh, baseArray[pos[u]] thường lưu giá trị của cạnh nối par[u] với u (nút u là nút sâu hơn).

Thông thường, người ta dùng một Segment Tree duy nhất cho tất cả các chuỗi nặng. Các chuỗi này sẽ chiếm các đoạn rời rạc trong baseArray chung.

Công Thức Truy Vấn Đường Đi Từ u Đến v:

Giờ là phần hấp dẫn nhất: làm sao để hỏi "đường từ u đến v có gì vui?" với HLD và Segment Tree? Giả sử chúng ta cần tính tổng các giá trị trên đường đi từ u đến v.

• Bước 0 (Nếu cần): Tìm "Trưởng Lão" Chung - LCA(u, v)

  • Trước khi chạy lung tung, phải biết "điểm hẹn chung" của u và v là ở đâu đã. Đó chính là Lowest Common Ancestor (LCA) – tổ tiên chung gần nhất của u và v.

• Bước 1: "Leo Thang" Từ u Lên LCA(u, v)

  • Mục tiêu là xử lý các đoạn đường đi từ u lên tới LCA. Ta sẽ "leo" dần lên theo từng chuỗi nặng.
  • Trong khi u và LCA(u, v) chưa cùng nằm trên một chuỗi nặng (tức là chainHead[u] khác chainHead[LCA(u,v)]):
    • Thực hiện truy vấn trên Segment Tree cho đoạn [pos[chainHead[u]], pos[u]]. Đây là phần đường đi nằm trên chuỗi nặng hiện tại của u.
    • Cộng kết quả truy vấn này vào tổng chung.
    • "Nhảy" u lên nút cha của đầu chuỗi hiện tại: u = par[chainHead[u]]. Thao tác này tương đương với việc đi qua một cạnh nhẹ để sang một chuỗi nặng khác, gần với LCA hơn.
  • Sau vòng lặp, u và LCA(u, v) đã cùng nằm trên một chuỗi nặng.
  • Thực hiện truy vấn trên Segment Tree cho đoạn còn lại: [pos[LCA(u,v)], pos[u]]. (Cẩn thận nếu LCA là u hoặc nếu truy vấn cạnh để tránh tính thừa).

• Bước 2: Tương Tự, "Leo Thang" Từ v Lên LCA(u, v)

  • Lặp lại quy trình tương tự như với u, nhưng lần này là "leo" từ v lên LCA(u, v).

• Bước 3: "Chốt Hạ" Kết Quả

  • Tổng các kết quả từ các truy vấn Segment Tree chính là đáp án.
  • Lưu ý quan trọng: Nếu LCA(u, v) không phải là u hay v ban đầu và anh em đang truy vấn giá trị nút, giá trị của LCA(u, v) có thể bị tính hai lần. Cần trừ đi một lần nếu thao tác là cộng tổng.

Độ Phức Tạp: Mỗi lần u (hoặc v) "nhảy" sang chuỗi khác là đi qua một cạnh nhẹ. Chúng ta biết có tối đa $O(\log N)$ cạnh nhẹ trên đường đi lên LCA. Mỗi đoạn trên chuỗi nặng được truy vấn bằng Segment Tree mất $O(\log N)$ thời gian. Do đó, tổng độ phức tạp cho một truy vấn đường đi là $O(\log^2 N)$. Quá đỉnh phải không anh em?

Cập Nhật Trên Đường Đi: Nếu bài toán yêu cầu cập nhật giá trị trên đường đi (ví dụ: cộng thêm một giá trị delta cho tất cả các nút/cạnh), quy trình hoàn toàn tương tự như truy vấn. Chỉ khác là thay vì query trên Segment Tree, anh em sẽ update trên các đoạn tương ứng.

Sự kết hợp giữa HLD và Segment Tree thực sự là một "cặp đôi hoàn hảo", biến bài toán đường đi trên cây thành một loạt các bài toán truy vấn đoạn trên mảng, nơi Segment Tree có thể "tung hoành".

4. HLD "Lên Sàn": Những Màn Trình Diễn "Bá Đạo"

HLD không chỉ là lý thuyết suông đâu anh em, mà nó là "vũ khí" cực mạnh trong thực tế và thi đấu lập trình.

• Ví Dụ 1: "Quy Hoạch Giao Thông Đô Thị"

  • Đề bài: Thành phố Mạng Nhện có N giao lộ, N-1 đường hai chiều, tạo thành một cây. Mỗi đường có "chi phí di chuyển". Thị trưởng Jim muốn:
    1. Truy vấn nhanh tổng chi phí đi lại giữa hai giao lộ u, v.
    2. Thỉnh thoảng, một con đường được "nâng cấp/xuống cấp", chi phí thay đổi.
  • Phân tích: Đây chính là bài toán truy vấn tổng trên đường đi và cập nhật giá trị cạnh. HLD + Segment Tree (lưu chi phí cạnh) là "chân ái"!
  • Cách làm:
    1. "Chặt cây" bằng HLD.
    2. Xây Segment Tree trên baseArray, với baseArray[pos[u]] lưu chi phí cạnh nối cha của u với u.
    3. Truy vấn thì "leo cây" như đã hướng dẫn ở phần 3.
    4. Cập nhật chi phí cạnh thì tìm nút con của cạnh đó rồi cập nhật trên Segment Tree tại vị trí pos tương ứng.
  • Ngoài lề: "Với HLD, thị trưởng Jim ngồi phòng lạnh bấm máy, biết tuốt chi phí mọi nẻo đường. Đường sá sửa chữa, HLD 'cân' tất! Tiết kiệm khối tiền thuê 'xe ôm' đo đường!"

• Ví Dụ 2: Các "Trùm Cuối" Trong Thi Đấu

  • QTREE - Query on a tree (SPOJ): Một series "huyền thoại". Ví dụ, QTREE yêu cầu tìm cạnh có trọng số lớn nhất trên đường đi giữa u, v và cho phép thay đổi trọng số cạnh. Đây là ứng dụng trực tiếp của HLD + Segment Tree (hỗ trợ tìm max và cập nhật điểm).
  • Cow Land (USACO Gold): Truy vấn XOR tổng giá trị nút trên đường đi và cập nhật giá trị nút. Lại là HLD + Segment Tree (hỗ trợ XOR sum và cập nhật điểm).
  • "Dân chuyên Tin chắc không lạ gì mấy 'em' này. HLD chính là chìa khóa vàng đấy!"

Khi Nào Thì "Triệu Hồi" HLD?

Hãy nghĩ ngay đến HLD khi anh em thấy các dấu hiệu:

• Bài toán trên cây.
• Yêu cầu nhiều truy vấn/cập nhật trên các đường đi bất kỳ.
• Các thao tác trên đường đi (tổng, min/max, XOR,...) có tính chất kết hợp (để Segment Tree "xử" được).
• Lo sợ duyệt cây chay cho mỗi truy vấn sẽ bị TLE (Time Limit Exceeded).
• "Nói chung, cứ thấy cây + đường đi + truy vấn nhiều + sợ TLE -> nhớ ngay đến HLD!"

5. "Bí Kíp" HLD: Mẹo Vặt & "Show Hàng" Code Nhẹ

Cài HLD lần đầu có thể hơi "xoắn não" với một mớ thông tin. Nhưng đừng lo, tôi có vài "mẹo" đây:

• Một Segment Tree "Cân" Tất Cả: Thay vì nhiều Segment Tree nhỏ cho mỗi chuỗi (phức tạp lắm!), cứ dùng một Segment Tree lớn duy nhất. Các chuỗi nặng sẽ chiếm các đoạn rời rạc trong baseArray mà Segment Tree này quản lý. "Một cây đại thụ Segment Tree quản lý hết các 'cao tốc', tiện lợi vô cùng!"
• Định Nghĩa Heavy Edge "Dễ Tính": Cứ chọn cạnh nối tới con có subtree size lớn nhất làm Heavy Edge. Dễ code hơn mà vẫn hiệu quả $O(\log N)$ cạnh nhẹ. "Cứ 'thằng con béo nhất' mà chọn, đời thanh thản."
• LCA "2 Trong 1": Có thể lồng logic tìm LCA vào quá trình "leo cây" khi truy vấn HLD luôn, đỡ phải gọi hàm riêng. "Một công đôi việc, vừa leo vừa ngó nghiêng tìm LCA, quá là hiệu quả!"

"Góc Khuất Hậu Trường" - Cẩn Thận Khi Code:

• Đánh Số pos Chuẩn Chỉnh: Cực kỳ quan trọng! Các nút trên cùng chuỗi nặng phải có pos liên tiếp. Thứ tự duyệt trong DFS 2 (ưu tiên Heavy Child) là chìa khóa.
• Quản Lý chainHead Chính Xác: Mỗi nút phải biết "sếp tổng" của chuỗi mình là ai.
• Xử Lý Nút LCA Tinh Tế: Coi chừng tính giá trị LCA hai lần (nếu truy vấn nút) hoặc tính sai cạnh.
• Cạnh Hay Đỉnh?: Xác định rõ truy vấn trên giá trị nút hay cạnh để biết baseArray[pos[u]] lưu gì.
• Chỉ Số Mảng (0-based vs 1-based): Nhất quán để tránh lỗi "trời ơi đất hỡi".
• "Code HLD lần đầu có thể hơi 'xoắn não', nhưng một khi đã thông, bạn sẽ thấy nó thật vi diệu. Cứ bình tĩnh, 'chia để trị' từng phần, và đừng quên print debug lia lịa!"

Checklist "Hành Trang" Cho Mỗi Nút:

(Nhá Hàng Code Nhẹ) DFS Tính Size, Depth, Parent, Heavy Child:

Đây là một đoạn C++ minh họa cho lượt DFS đầu tiên:

const int MAXN = 100005; // Giả sử số nút tối đa
vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN], subtreeSize[MAXN];
int heavyChild[MAXN]; // DfsSize: Tính toán kích thước cây con, độ sâu, cha, và con nặng
// u: nút hiện tại
// p: cha của nút hiện tại
// d: độ sâu hiện tại
void DfsSize(int u, int p, int d)
{ parent[u] = p; // Lưu cha của u depth[u] = d; // Lưu độ sâu của u subtreeSize[u] = 1; // Khởi tạo kích thước cây con của u là 1 (chính nó) heavyChild[u] = -1; // Khởi tạo chưa có con nặng (-1 nghĩa là không có) int maxSubTreeSize = 0; // Kích thước cây con lớn nhất của các con của u for (int v : adj[u]) { // Duyệt qua các con v của u if (v == p) continue; // Bỏ qua nút cha DfsSize(v, u, d + 1); // Đệ quy xuống con v subtreeSize[u] += subtreeSize[v]; // Cộng dồn kích thước cây con của v vào u // Kiểm tra xem v có phải là con "béo" nhất hiện tại không if (subtreeSize[v] > maxSubTreeSize) { maxSubTreeSize = subtreeSize[v]; heavyChild[u] = v; // Cập nhật con nặng là v } }
}

"Đây chỉ là 'mảnh ghép' khởi động thôi nhé, đừng thấy ngắn mà khinh thường, nó là nền móng cho cả một 'đế chế' đấy!"

6. Lời Kết: "Chinh Phục" HLD - Giờ Thì "Quẩy" Thôi Anh Em!

Vậy là chúng ta đã cùng nhau "bóc mẽ" Heavy-Light Decomposition từ A đến Z! Từ những khái niệm "nặng nhẹ" cơ bản, cách HLD "chặt cây" thông minh, đến màn "song kiếm hợp bích" với Segment Tree.

Hy vọng qua những giải thích và ví dụ có phần "hóm hỉnh" của tôi, anh em đã thấy HLD không còn đáng sợ nữa. Sức mạnh của HLD nằm ở việc giảm độ phức tạp truy vấn đường đi từ $O(N)$ xuống còn $O(\log^2 N)$ (hoặc $O(\log N)$ nếu "pro" hơn), một cải tiến cực kỳ đáng kể.

Giờ anh em đã có đủ "vũ khí" để chinh phục những bài toán cây hóc búa rồi đấy. Đừng ngần ngại thử sức thực hành, đó là cách tốt nhất để HLD "ngấm vào máu".

Chúc anh em có những giờ phút "quẩy" HLD thật vui và hiệu quả! Và nhớ, nếu có lỡ "lạc trôi" trong rừng cây thuật toán, hãy nhớ rằng luôn có những "cao tốc" HLD sẵn sàng dẫn lối!

HLD – không chỉ "nặng" về tên gọi, mà còn "nặng" về sức mạnh! Hãy dùng nó để làm cho code của anh em "nhẹ" gánh hơn nhé!