Thi đấu

Kỹ Thuật Gộp Nhỏ Vào Lớn Trên Cây (DSU on Tree / Sack)

DSU on Tree (còn gọi là Sack hay Small to Large trên cây) là kỹ thuật tối ưu hóa quy hoạch động trên cây giúp trả lời các truy vấn cây con trong thời gian O(N log N) với bộ nhớ O(N) phẳng.

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)\)!

KỸ THUẬT GỘP NHỎ VÀO LỚN TRÊN CÂY (DSU ON TREE / SACK) Trả lời mọi truy vấn cây con trong O(N log N) bằng một mảng tần số toàn cục duy nhất Quy trình xử lý đỉnh u u Con nhẹ v₁ keep = false(xóa sau khi tính) Con nặng (Heavy) keep = true(giữ lại mảng cnt) Duyệt lại con nhẹ gộp vào cnt Mảng tần số toàn cục cnt[] TRẠNG THÁI MẢNG CNT[]: cnt[màu 1] = 2, cnt[màu 2] = 1 CHỨNG MINH O(N log N): • Mỗi đỉnh chỉ bị thêm lại khi nónằm trong một cây con nhẹ. • Mỗi đỉnh có ≤ log₂ N tổ tiên nhẹ. ⇒ Tổng số lần thêm đỉnh: ≤ N log₂ N ƯU ĐIỂM CỐT LÕI CỦA DSU ON TREE: Không dùng con trỏ/map động • Bộ nhớ O(N) phẳng • Thời gian O(N log N) với hằng số nhỏ.
DSU ON TREE (SACK) Gộp nhỏ vào lớn trên cây trong O(N log N) Quy trình xử lý đỉnh u u Con nhẹ keep = false Con nặng keep = true → Duyệt lại con nhẹ gộp vào mảng cnt[] TẠI SAO ĐẠT O(N log N)? • Mỗi đỉnh chỉ bị thêm lại khi nằm trong con nhẹ. • Số lượng tổ tiên nhẹ ≤ log₂ N. ⇒ Tổng số phép thêm đỉnh ≤ N log₂ N ƯU THẾ THI ĐẤU: • Bộ nhớ O(N) phẳng, không cấp phát động. • Cài đặt ngắn gọn chỉ với 2 hàm DFS.
Quy trình thực thi DSU on Tree với cờ keep và chứng minh độ phức tạp O(N log 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:

  1. 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.
  2. 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:

  1. 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[]
        }
    }
    
  2. 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[]
    }
    
  3. 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 trong cnt[], 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ào cnt[]:
    add_subtree(u, p, +1, heavy[u]); // Duyệt mọi đỉnh trong con của u trừ con nặng
    
  4. 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.
    
  5. 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ảng cnt[]) 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.

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 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;
}

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

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