Kỹ Thuật Gộp Nhỏ Vào Lớn Trên Cây (DSU on Tree / Sack)
Khi giải các bài toán trên cấu trúc cây (Tree) trong các kỳ thi Codeforces hay Olympic Tin học, một dạng đề bài xuất hiện rất thường xuyên là: Truy vấn thống kê thông tin trên từng cây con (Subtree Queries). Ví dụ:
- Với mỗi đỉnh \(u\), đếm số lượng màu sắc phân biệt của các đỉnh nằm trong cây con của \(u\).
- Với mỗi đỉnh \(u\), tìm màu sắc xuất hiện nhiều lần nhất trong cây con của \(u\).
- Đếm số cặp đỉnh trong cây con có độ sâu \(k\) hoặc thỏa mãn điều kiện bitmask.
Nếu duyệt DFS độc lập cho từng đỉnh, độ phức tạp sẽ là \(O(N^2)\) — chắc chắn nhận Time Limit Exceeded (TLE) khi \(N = 10^5\). Nếu dùng cấu trúc std::map hoặc std::set để gộp từ con lên cha theo kỹ thuật Small to Large (gộp tập nhỏ vào tập lớn), độ phức tạp là \(O(N \log^2 N)\) nhưng lại tiêu tốn rất nhiều bộ nhớ động và chạy chậm do chi phí cấp phát node của cây đỏ đen.
DSU on Tree (còn được cộng đồng quốc tế gọi thân mật là thuật toán Sack theo bài viết nổi tiếng của tác giả Arpa trên Codeforces) là một kỹ thuật tuyệt đẹp: Nó cho phép bạn trả lời mọi truy vấn cây con trong thời gian \(O(N \log N)\) mà chỉ dùng một mảng tần số toàn cục phẳng duy nhất \(O(N)\)!
Tư tưởng cốt lõi: Con nặng (Heavy) và Con nhẹ (Light)
Tương tự như trong kỹ thuật Phân rã cây Heavy-Light Decomposition (HLD), DSU on Tree chia các đỉnh con của mỗi đỉnh \(u\) thành hai loại:
- Con nặng (Heavy Child): Đỉnh con \(v\) có kích thước cây con \(\text{sz}[v]\) lớn nhất trong tất cả các con của \(u\). Mỗi đỉnh có tối đa 1 con nặng.
- Con nhẹ (Light Children): Tất cả các đỉnh con còn lại của \(u\).
Giả sử ta có một mảng đếm tần số toàn cục cnt[color] dùng chung cho toàn bộ chương trình:
- Khi xử lý một cây con, ta cập nhật tần số các đỉnh vào
cnt[]và ghi nhận kết quả. - Nhưng khi chuyển sang một cây con độc lập khác, ta phải xóa sạch (clear) dữ liệu vừa thêm vào
cnt[]để tránh làm sai lệch kết quả của cây con bên cạnh!
Ý tưởng đột phá của DSU on Tree nằm ở câu hỏi: Tại sao phải xóa sạch dữ liệu của tất cả các con?
- Con nặng là con có kích thước lớn nhất (chứa nhiều đỉnh nhất).
- Nếu ta tính toán con nặng cuối cùng, ta có thể GIỮ LẠI (keep) toàn bộ thông tin của cây con nặng trên mảng
cnt[]mà không cần xóa đi! - Sau đó, ta chỉ cần duyệt lại các cây con nhẹ (vốn có kích thước nhỏ hơn nhiều) để bổ sung thêm vào
cnt[]. - Tiết kiệm được toàn bộ công sức thêm và xóa cho cây con nặng nhất!
Quy trình thuật toán với cờ keep
Thuật toán gồm hai hàm DFS cực kỳ thanh lịch:
Bước 1: Tính kích thước cây con dfs_size(u, p)
Duyệt DFS từ gốc để tính \(\text{sz}[u]\) và tìm đỉnh con nặng \(\text{heavy}[u]\) cho mọi đỉnh \(u\).
Bước 2: Hàm đệ quy chính dfs_sack(u, p, keep)
Hàm nhận tham số keep (kiểu boolean), cho biết liệu sau khi tính xong cây con gốc \(u\), dữ liệu của nó có được giữ lại trên mảng toàn cục cnt[] cho đỉnh cha dùng tiếp hay không:
- Duyệt tất cả các con nhẹ trước tiên với
keep = false:for (int v : adj[u]) { if (v != p && v != heavy[u]) { dfs_sack(v, u, false); // Tính xong kết quả của v, sau đó tự xóa sạch cnt[] } } - Duyệt con nặng duy nhất với
keep = true:if (heavy[u] != 0) { dfs_sack(heavy[u], u, true); // Tính xong con nặng và GIỮ NGUYÊN cnt[] } - Bổ sung đỉnh \(u\) và các cây con nhẹ vào
cnt[]: Vì dữ liệu của con nặng đã có sẵn trongcnt[], ta chỉ cần duyệt lại các cây con nhẹ của \(u\) và đỉnh \(u\) để cộng dồn vàocnt[]:add_subtree(u, p, +1, heavy[u]); // Duyệt mọi đỉnh trong con của u trừ con nặng - Trả lời và lưu kết quả cho đỉnh \(u\):
Lúc này, mảng
cnt[]đang chứa đầy đủ và chính xác \(100\%\) dữ liệu của toàn bộ cây con gốc \(u\). Ta ghi nhận đáp án:ans[u] = distinct_colors; // Hoặc max_frequency, sum, v.v. - Xóa dữ liệu nếu đỉnh \(u\) là con nhẹ (
keep == false): Nếu đỉnh cha không cần giữ lại dữ liệu của \(u\), ta xóa toàn bộ cây con của \(u\) khỏi mảng:if (!keep) { add_subtree(u, p, -1, 0); // Trừ hết về 0 }
Chứng minh độ phức tạp O(N log N)
Tại sao thuật toán duyệt lại các cây con nhẹ mà không bị quá thời gian?
Hãy quan sát một đỉnh \(x\) bất kỳ trên cây:
- Đỉnh \(x\) chỉ bị duyệt lại (gọi hàm
add_subtreeđể cộng vào hoặc trừ ra khỏi mảngcnt[]) khi và chỉ khi: đỉnh \(x\) nằm trong một cây con nhẹ của một tổ tiên \(A\) nào đó của nó. - Nếu \(x\) nằm trong nhánh con nặng của tổ tiên, dữ liệu của nó được giữ nguyên và không bao giờ bị duyệt lại ở cấp tổ tiên đó!
- Theo tính chất của cạnh nhẹ trong cây: Mỗi lần bước qua một cạnh nhẹ lên cha, kích thước cây con ít nhất tăng gấp đôi (\(\text{sz}[\text{cha}] \gt 2 \cdot \text{sz}[\text{con}]\)).
- Do cây có \(N\) đỉnh, một đỉnh \(x\) có tối đa \(\lfloor \log_2 N \rfloor\) tổ tiên nhẹ!
Định lý thời gian DSU on Tree: Mỗi đỉnh \(x\) chỉ bị thêm vào và xóa khỏi mảng toàn cục tối đa \(O(\log N)\) lần trong suốt toàn bộ quá trình thực thi. Với \(N\) đỉnh, tổng số thao tác trên mảng toàn cục là: \[O(N \log N)\]
Vì mỗi thao tác trên mảng cnt[] tốn \(O(1)\), tổng thời gian chạy của DSU on Tree là \(O(N \log N)\)!
Bản chất chứng minh độ phức tạp O(N log N) của DSU on Tree
Nhiều bạn học sinh khi mới tiếp cận DSU on Tree thường lo ngại rằng việc xóa toàn bộ dữ liệu của các nhánh con nhẹ sẽ khiến thuật toán bị thoái hóa về \(O(N^2)\) trong trường hợp cây là một đường thẳng hoặc cây phân nhánh sâu.
Tuy nhiên, bằng cách phân tích kỹ thuật phân rã cạnh Nặng - Nhẹ (Heavy-Light Decomposition):
- Một đỉnh \(u\) chỉ bị thêm vào và xóa khỏi mảng tần số khi nó nằm trong một cây con nhẹ của một tổ tiên nào đó.
- Cạnh nối từ đỉnh con nhẹ lên đỉnh cha được gọi là một cạnh nhẹ (Light Edge). Theo tính chất cây, kích thước cây con của con nhẹ luôn thỏa mãn: \[\text{sz}[\mathrm{v\_light}] \le \frac{1}{2} \text{sz}[u]\]
- Do kích thước cây con ít nhất phải tăng gấp đôi sau mỗi lần bước qua một cạnh nhẹ, trên bất kỳ đường đi nào từ gốc cây tới một lá bất kỳ, một đỉnh chỉ có thể đi qua tối đa \(\lfloor \log_2 N \rfloor\) cạnh nhẹ!
- Điều đó đồng nghĩa với việc: Trong suốt toàn bộ quá trình chạy của thuật toán trên toàn cây, mỗi đỉnh chỉ bị "xóa đi và thêm lại" tối đa \(O(\log N)\) lần!
Tổng số phép tính thêm và xóa trên toàn bộ \(N\) đỉnh bị chặn cứng bởi: \[N \times O(\log N) = O(N \log N)\] Đây là một kết quả toán học vững chắc, đảm bảo thời gian \(O(N \log N)\) với mọi hình dạng cây (kể cả cây suy biến thành đường thẳng, cây sao hay cây nhị phân hoàn chỉnh). Riêng cây suy biến thành đường thẳng làm các hàm đệ quy sâu tới \(N\) tầng: với \(N\) cỡ \(10^5\) đến \(2 \cdot 10^5\) và giới hạn stack 8 MB, bản C++ đệ quy có thể bị tràn stack (Runtime Error). Khi đó cần viết DFS không đệ quy, hoặc tăng giới hạn stack nếu hệ chấm cho phép.
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 chuẩn C++17 và Python 3
Dưới đây là lời giải mẫu hoàn chỉnh được kiểm thử kỹ lưỡng, tối ưu I/O và sẵn sàng nộp trên hệ thống:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Cấu trúc DSU on Tree (Sack) đếm số màu phân biệt trong cây con của mọi đỉnh
// Độ phức tạp thời gian: O(N log N)
// Độ phức tạp bộ nhớ: O(N)
const int MAXN = 200005;
int n;
int color[MAXN];
vector<int> adj[MAXN];
int sz[MAXN], heavy[MAXN];
int cnt[MAXN];
int distinct_colors = 0;
int ans[MAXN];
// DFS 1: Tính kích thước cây con và tìm đỉnh con nặng
void dfs_size(int u, int p) {
sz[u] = 1;
int max_c = 0;
for (int v : adj[u]) {
if (v != p) {
dfs_size(v, u);
sz[u] += sz[v];
if (sz[v] > max_c) {
max_c = sz[v];
heavy[u] = v;
}
}
}
}
// Hàm thêm hoặc xóa đỉnh trong cây con vào mảng tần số toàn cục
void add_subtree(int u, int p, int x, int big_child) {
if (cnt[color[u]] == 0 && x == 1) {
distinct_colors++;
}
cnt[color[u]] += x;
if (cnt[color[u]] == 0 && x == -1) {
distinct_colors--;
}
for (int v : adj[u]) {
if (v != p && v != big_child) {
add_subtree(v, u, x, big_child);
}
}
}
// DFS 2: Thuật toán DSU on Tree
void dfs_sack(int u, int p, bool keep) {
// 1. Duyệt tất cả các con nhẹ và KHÔNG giữ lại thông tin
for (int v : adj[u]) {
if (v != p && v != heavy[u]) {
dfs_sack(v, u, false);
}
}
// 2. Duyệt con nặng duy nhất và GIỮ lại thông tin
if (heavy[u] != 0) {
dfs_sack(heavy[u], u, true);
}
// 3. Thêm đỉnh u và các cây con nhẹ vào mảng tần số
add_subtree(u, p, 1, heavy[u]);
// 4. Lưu kết quả truy vấn cho cây con gốc u
ans[u] = distinct_colors;
// 5. Nếu đỉnh u là con nhẹ của cha nó (keep == false), xóa toàn bộ cây con u
if (!keep) {
add_subtree(u, p, -1, 0);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n)) return 0;
for (int i = 1; i <= n; i++) {
cin >> color[i];
}
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs_size(1, 0);
dfs_sack(1, 0, true);
for (int i = 1; i <= n; i++) {
cout << ans[i] << (i == n ? "" : " ");
}
cout << "\n";
return 0;
}
import sys
# Tăng giới hạn đệ quy
sys.setrecursionlimit(300000)
def main():
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
color = [0] + [int(x) for x in input_data[1:n + 1]]
idx = n + 1
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u = int(input_data[idx])
v = int(input_data[idx + 1])
idx += 2
adj[u].append(v)
adj[v].append(u)
sz = [0] * (n + 1)
heavy = [0] * (n + 1)
def dfs_size(u, p):
sz[u] = 1
max_c = 0
for v in adj[u]:
if v != p:
dfs_size(v, u)
sz[u] += sz[v]
if sz[v] > max_c:
max_c = sz[v]
heavy[u] = v
dfs_size(1, 0)
# Tìm giá trị màu lớn nhất để khởi tạo mảng cnt
max_c_val = max(color)
cnt = [0] * (max_c_val + 1)
distinct_colors = 0
ans = [0] * (n + 1)
def add_subtree(u, p, x, big_child):
nonlocal distinct_colors
c = color[u]
if cnt[c] == 0 and x == 1:
distinct_colors += 1
cnt[c] += x
if cnt[c] == 0 and x == -1:
distinct_colors -= 1
for v in adj[u]:
if v != p and v != big_child:
add_subtree(v, u, x, big_child)
def dfs_sack(u, p, keep):
for v in adj[u]:
if v != p and v != heavy[u]:
dfs_sack(v, u, False)
if heavy[u] != 0:
dfs_sack(heavy[u], u, True)
add_subtree(u, p, 1, heavy[u])
ans[u] = distinct_colors
if not keep:
add_subtree(u, p, -1, 0)
dfs_sack(1, 0, True)
sys.stdout.write(" ".join(map(str, ans[1:n + 1])) + "\n")
if __name__ == '__main__':
main()
So sánh DSU on Tree với các phương pháp khác
| Phương pháp | Thời gian | Bộ nhớ | Đánh giá |
|---|---|---|---|
| DFS vét cạn mỗi đỉnh | \(O(N^2)\) | \(O(N)\) | Quá chậm, chỉ ăn điểm subtask \(N \le 1000\). |
Gộp std::set / std::map (Small to Large) |
\(O(N \log^2 N)\) | \(O(N \log N)\) | Tốn bộ nhớ động, dễ dính MLE hoặc chậm do cache miss. |
| Mo's algorithm on Tree (Euler Tour) | \(O(N \sqrt{Q})\) | \(O(N)\) | Cần sắp xếp truy vấn offline, code dài hơn DSU on Tree. |
| DSU on Tree (Sack) | \(O(N \log N)\) | \(O(N)\) | Tối ưu tuyệt đối về tốc độ và bộ nhớ, cài đặt ngắn gọn. |
Luyện ngay trên Big-O Coding
Để củng cố kiến thức và kiểm tra trực tiếp độ chính xác của chương trình, bạn hãy thực hành ngay bài tập sau trên hệ thống Big-O Coding, đúng bài toán đếm số màu khác nhau trong mỗi cây con mà code ở trên giải:
Khi nào nên dùng DSU on Tree và khi nào dùng HLD?
DSU on Tree chuyên trị các bài toán truy vấn trên toàn bộ cây con (Subtree queries) có tính chất offline, gom cụm dữ liệu phức tạp (như mảng tần số, bitset, tính chất tập hợp) mà không thể biểu diễn gọn bằng một hàm kết hợp đơn giản trên Segment Tree. Ngược lại, HLD chuyên dùng cho các bài toán truy vấn và cập nhật trên đường đi (Path queries) giữa hai đỉnh bất kỳ \((u, v)\).
Có thể dùng thứ tự Euler Tour để duyệt mảng phẳng thay cho hàm đệ quy add_subtree không?
Hoàn toàn được! Bằng cách trải phẳng cây qua mảng Euler Tour (\(tin[u]\) và \(tout[u]\)), toàn bộ cây con của \(u\) trở thành một đoạn liên tiếp \([tin[u], tout[u]]\) trên mảng phẳng. Thay vì gọi đệ quy add_subtree, bạn có thể dùng một vòng lặp for (int i = tin[v]; i <= tout[v]; i++) để thêm đỉnh, giúp tăng tốc độ thực thi thêm khoảng \(30\%\).
Nếu giá trị màu lên tới \(10^9\) thì xử lý mảng cnt[] thế nào?
Vì cây chỉ có tối đa \(N\) đỉnh nên tổng số màu thực tế xuất hiện không bao giờ vượt quá \(N\). Hãy thực hiện nén số (Coordinate Compression) trước khi chạy DSU on Tree để ánh xạ toàn bộ các giá trị màu về đoạn \([1, N]\), cho phép dùng trực tiếp mảng nguyên cnt[MAXN].
Nguồn tham khảo
- Codeforces Blog - DSU on Tree tutorial by Arpa - Bài viết gốc khai sinh tên gọi Sack và cách tiếp cận kinh điển.
- VNOI Wiki - Heavy-Light Decomposition (HLD) - Khái niệm con nặng, con nhẹ và chứng minh mỗi đường đi lên gốc qua không quá O(log N) cạnh nhẹ, nền tảng của phép chứng minh độ phức tạp ở bài này.
- USACO Guide - Small-To-Large Merging - Gộp nhỏ vào lớn trên cây con, ví dụ đếm số màu khác nhau trong mỗi cây con, kèm bài tập.
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.


