DSU on Tree (Small to Large)

Wiki › Cấu trúc dữ liệu › Cây

huunguyen · Last updated 8, Tháng 4, 2026, 15:24

DSU on Tree (còn gọi là Small to Large merging hoặc Sack) là kỹ thuật trả lời các truy vấn về cây con trong $O (N \log N)$ bằng cách tận dụng heavy child để tránh sao chép thừa.

Ứng dụng: Đếm số màu phân biệt trong cây con, tìm giá trị xuất hiện nhiều nhất trong cây con, tổng các giá trị phân biệt, v.v.

Hai cách tiếp cận

1. Small to Large (Merging)

Khi merge hai tập, luôn merge tập nhỏ vào tập lớn. Mỗi phần tử bị merge $O (\log N)$ lần.

// Ví dụ: đếm số giá trị phân biệt trong mỗi cây con
vector<int> val(n+1);
vector<set<int>*> S(n+1);

void dfs(int u, int p) {
    S[u] = new set<int>();
    S[u]->insert(val[u]);

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        // Merge tập nhỏ vào tập lớn
        if (S[v]->size() > S[u]->size()) swap(S[u], S[v]);
        for (int x : *S[v]) S[u]->insert(x);
        delete S[v];
    }
    ans[u] = S[u]->size();
}

Độ phức tạp: $O (N \log^{2} N)$ với set, $O (N \log N)$ với unordered_set.

2. DSU on Tree (Euler Tour + Heavy Child)

Phiên bản hiệu quả hơn, đặc biệt khi cần giữ thông tin đa dạng:

// Trả lời: với mỗi đỉnh u, tổng số đỉnh trong cây con u có giá trị = mode (giá trị xuất hiện nhiều nhất)
int sz[MAXN], heavy[MAXN];
int cnt[MAXN];    // cnt[v] = số lần giá trị v xuất hiện trong tập đang xét
int cur_max = 0, cur_ans = 0;
long long ans[MAXN];
int val[MAXN];

// Bước 1: tính heavy child
int dfs_sz(int u, int p) {
    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);
        if (sz[v] > max_sz) { max_sz = sz[v]; heavy[u] = v; }
    }
    return sz[u];
}

void add(int u, int p, int sign) {
    cnt[val[u]] += sign;
    if (sign > 0) {
        if (cnt[val[u]] > cur_max) { cur_max = cnt[val[u]]; cur_ans = u; }
        // cập nhật tuỳ bài
    }
    for (int v : adj[u])
        if (v != p) add(v, u, sign);
}

// Bước 2: DSU on Tree
void dfs(int u, int p, bool keep) {
    // Xử lý light children trước (xóa sau)
    for (int v : adj[u]) {
        if (v == p || v == heavy[u]) continue;
        dfs(v, u, false);
    }
    // Xử lý heavy child (giữ lại)
    if (heavy[u] != -1) dfs(heavy[u], u, true);

    // Thêm các light children vào tập
    for (int v : adj[u]) {
        if (v == p || v == heavy[u]) continue;
        add(v, u, +1);
    }
    add(u, p, +1);   // thêm bản thân u

    ans[u] = cur_ans;   // lưu kết quả cho u

    // Nếu không giữ, xóa toàn bộ cây con
    if (!keep) {
        add(u, p, -1);
        cur_max = 0; cur_ans = 0;
    }
}

Độ phức tạp

Phương pháp	Thời gian	Ghi chú
Small to Large (set)	$O (N \log^{2} N)$	Dễ cài, linh hoạt
DSU on Tree	$O (N \log N)$	Nhanh hơn, phù hợp offline

Cả hai đều dùng bộ nhớ $O (N)$ .

Khi nào dùng DSU on Tree?

Truy vấn về cây con: đếm phân biệt, mode, tổng...
Bài toán offline (không cập nhật cây).
Thay thế $O (N^{2})$ brute force duyệt mọi cây con.

Bình luận

Không có bình luận tại thời điểm này.