Centroid Decomposition

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

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

Centroid Decomposition (phân rã trọng tâm) là kỹ thuật chia cây đệ quy theo centroid, cho phép giải các bài toán về đường đi trong cây trong $O (N \log^{2} N)$ hoặc $O (N \log N)$ .

Centroid của cây là đỉnh mà khi xóa đi, mọi thành phần liên thông còn lại có kích thước $\leq N / 2$ . Mọi cây đều có ít nhất một centroid.

Ứng dụng:

Đếm số đường đi có tổng trọng số bằng $k$ .
Tìm đường đi ngắn nhất thỏa điều kiện.
Bài toán truy vấn khoảng cách offline trong cây.

Ý tưởng

Tìm centroid $c$ của cây hiện tại.
Xử lý tất cả đường đi đi qua $c$ .
Đánh dấu $c$ đã xử lý (removed), đệ quy vào các cây con còn lại.

Tính chất: Mỗi đỉnh xuất hiện trong $O (\log N)$ cây con centroid → tổng công là $O (N \log N)$ (hoặc $O (N \log^{2} N)$ nếu mỗi bước cần $O (\log N)$ ).

Cài đặt

const int MAXN = 2e5 + 5;
vector<pair<int,int>> adj[MAXN];   // {neighbor, weight}
int sz[MAXN];
bool removed[MAXN];

// Tính kích thước cây con
int get_size(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v])
            sz[u] += get_size(v, u);
    return sz[u];
}

// Tìm centroid của cây gốc u có tổng kích thước tree_sz
int get_centroid(int u, int p, int tree_sz) {
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v] && sz[v] > tree_sz / 2)
            return get_centroid(v, u, tree_sz);
    return u;
}

// Thu thập tất cả khoảng cách từ centroid c xuống cây con
void collect(int u, int p, int dist, vector<int>& dists) {
    dists.push_back(dist);
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v])
            collect(v, u, dist + w, dists);
}

// Xử lý tất cả đường đi đi qua centroid c
// (tùy bài toán — ví dụ: đếm đường đi có độ dài = K)
int K;
long long ans = 0;

void solve(int u) {
    get_size(u, -1);
    int c = get_centroid(u, -1, sz[u]);
    removed[c] = true;

    // Thu thập khoảng cách từ c đến tất cả đỉnh trong cây
    vector<int> all_dists = {0};   // bản thân c có dist = 0
    for (auto [v, w] : adj[c]) {
        if (removed[v]) continue;
        vector<int> sub;
        collect(v, c, w, sub);
        // Đếm cặp (d1 từ lần trước, d2 từ lần này) với d1 + d2 = K
        for (int d : sub)
            if (K - d >= 0)
                /* ans += count of (K-d) in all_dists (dùng sort + binary search) */;
        for (int d : sub) all_dists.push_back(d);
    }

    // Đệ quy các cây con
    for (auto [v, w] : adj[c])
        if (!removed[v])
            solve(v);
}

Ví dụ: Đếm đường đi có độ dài K

long long count_paths(int u) {
    get_size(u, -1);
    int c = get_centroid(u, -1, sz[u]);
    removed[c] = true;

    vector<int> all = {0};
    long long res = 0;

    for (auto [v, w] : adj[c]) {
        if (removed[v]) continue;
        vector<int> sub;
        collect(v, c, w, sub);

        sort(all.begin(), all.end());
        for (int d : sub) {
            int need = K - d;
            res += upper_bound(all.begin(), all.end(), need)
                 - lower_bound(all.begin(), all.end(), need);
        }
        for (int d : sub) all.push_back(d);
    }

    for (auto [v, w] : adj[c])
        if (!removed[v])
            res += count_paths(v);

    return res;
}

Độ phức tạp

	Độ phức tạp
Tìm centroid	$O (N)$ mỗi lần
Số lần tìm centroid	$O (\log N)$ levels
Xử lý mỗi level	$O (N \log N)$ (sort) hoặc $O (N)$
Tổng	$O (N \log^{2} N)$ hoặc $O (N \log N)$

Khi nào dùng Centroid Decomposition?

Bài toán về đường đi trong cây (tổng, count, shortest).
Khi cần xử lý mọi cặp đỉnh trong cây hiệu quả.
Cây cố định — nếu cây thay đổi, dùng Link-Cut Tree.

Bình luận

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