Centroid Decomposition

Centroid Decomposition (phân rã trọng tâm) là kỹ thuật đệ quy chia cây theo trọng tâm (centroid), biến mọi bài toán về đường đi trong cây thành bài toán "đường đi đi qua một đỉnh cố định". Nhờ đó, thay vì duyệt tất cả $O(N^2)$ cặp đỉnh một cách ngây thơ, ta xử lý mọi cặp trong $O(N\log N)$ hoặc $O(N{\log }^{2}N)$.

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

Ứng dụng tiêu biểu:

• Đếm số đường đi có độ dài (số cạnh / tổng trọng số) bằng $k$.
• Đếm số cặp đỉnh có khoảng cách $\le k$.
• Truy vấn khoảng cách / cập nhật trên cây tĩnh (cây centroid làm "khung" để gắn cấu trúc dữ liệu lên mỗi đỉnh).

Ý tưởng / Trực giác

Câu hỏi cốt lõi: làm sao xét hết mọi đường đi trên cây mà không bị $O(N^2)$?

Quan sát then chốt: lấy bất kỳ đỉnh $c$ nào, mọi đường đi trên cây chia làm hai nhóm:

1. Đường đi đi qua $c$ (tức $c$ nằm trên đường đi, kể cả là một đầu mút).
2. Đường đi không chạm $c$ — đường đi này nằm gọn trong một thành phần liên thông sau khi xóa $c$.

Với nhóm 1, mỗi đường đi qua $c$ luôn ghép từ hai "nửa đường" đi từ $c$ xuống hai nhánh con khác nhau (hoặc một nửa nếu $c$ là đầu mút). Ta có thể duyệt từ $c$ xuống toàn bộ cây, gom thông tin (vd khoảng cách), rồi đếm các cặp nửa-đường hợp lệ — chi phí $O(\text{size})$ hoặc $O(\text{size}\log \text{size})$.

Với nhóm 2, ta đệ quy: xóa $c$, mỗi thành phần liên thông trở thành cây con và được xử lý y hệt.

Tại sao phải chọn $c$ là centroid chứ không phải đỉnh bất kỳ? Vì độ sâu đệ quy quyết định tổng chi phí. Nếu chọn bừa (ví dụ luôn chọn gốc của một cây hình "đường thẳng"), độ sâu đệ quy có thể tới $N$ và tổng công lại bùng về $O(N^2)$. Khi chọn centroid, mỗi cây con có kích thước $\le N/2$, nên cây đệ quy chỉ sâu $O(\log N)$ tầng.

Tính chất quan trọng (bất biến $O(\log N)$): mỗi đỉnh chỉ xuất hiện trong $O(\log N)$ cây con centroid (một lần ở mỗi tầng đệ quy). Tổng kích thước tất cả cây con ở một tầng $\le N$, nhân $O(\log N)$ tầng ra tổng $O(N\log N)$ công duyệt.

Ví dụ chạy tay

Xét cây 7 đỉnh, mọi cạnh trọng số 1. Bài toán: đếm số đường đi có đúng $K=2$ cạnh.

            1
            |
            2
          / | \
         3  4  5
               |
               6
               |
               7

Tầng 0 — tìm centroid của cả cây ($N=7$):

Tính kích thước cây con (gốc giả tại 1) rồi đi xuống nhánh "nặng" $>7/2=3$. Đỉnh 2 thoả: xóa 2, các thành phần là $\{1\}$(1), $\{3\}$(1), $\{4\}$(1), $\{5,6,7\}$(3) — tất cả $\le 3$. Vậy centroid là 2.

         centroid = 2   (đánh dấu removed)
        /  |  \   \
      [1] [3] [4] [5-6-7]

Gom khoảng cách từ 2 xuống từng nhánh, đếm cặp tổng $=K=2$. Duy trì danh sách all các khoảng cách đã thấy (khởi tạo {0} cho chính đỉnh 2):

Tổng đường đi qua centroid 2 (độ dài 2): $0+1+2+4=7$.

Tầng 1 — đệ quy vào thành phần $\{5,6,7\}$ (các thành phần 1 đỉnh không có đường đi):

   5 - 6 - 7     N = 3, centroid = 6

Gom từ centroid 6: nhánh 5 cho [1], nhánh 7 cho [1]. Cặp tổng $=2$: đường 5–6–7. Thêm 1 đường.

Kết quả: $7+1=8$ đường đi có đúng 2 cạnh. (Lưu ý cách đếm trên tính mỗi đường một lần vì hai đầu mút luôn rơi vào hai nhánh xử lý ở thời điểm khác nhau, hoặc một đầu là chính centroid.)

Cài đặt

Mẫu dưới đếm số đường đi có tổng trọng số đúng bằng $K$ (đổi +w thành +1 nếu đếm theo số cạnh). Mấu chốt để không đếm lặp trong cùng một nhánh: xử lý từng nhánh con của centroid lần lượt, đối chiếu với all (gom từ các nhánh trước đó) rồi mới nạp nhánh hiện tại vào all.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
vector<pair<int,int>> adj[MAXN];   // {đỉnh kề, trọng số}
int sz[MAXN];
bool removed[MAXN];                 // đã bị xóa khỏi cây?
long long K;
long long ans = 0;

// Tính kích thước cây con (bỏ qua đỉnh đã removed)
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: đi xuống nhánh có kích thước > tree_sz/2
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;
}

// Gom khoảng cách từ centroid xuống một nhánh
void collect(int u, int p, long long dist, vector<long long>& out) {
    out.push_back(dist);
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v])
            collect(v, u, dist + w, out);
}

void decompose(int root) {
    get_size(root, -1);
    int c = get_centroid(root, -1, sz[root]);
    removed[c] = true;                 // xóa centroid khỏi cây

    // all chứa khoảng cách từ c đến mọi đỉnh ở CÁC NHÁNH ĐÃ XÉT (gồm cả c: dist 0)
    multiset<long long> all = {0};

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

        // Đếm cặp (d_cũ, d_mới) với d_cũ + d_mới = K -> chỉ ghép NHÁNH KHÁC nhau
        for (long long d : sub)
            ans += all.count(K - d);

        // Nạp nhánh hiện tại vào all SAU khi đã đếm
        for (long long d : sub) all.insert(d);
    }

    // Đệ quy các thành phần liên thông còn lại
    for (auto [v, w] : adj[c])
        if (!removed[v])
            decompose(v);
}

multiset::count chậm; trong thực tế nên thay bằng vector đã sort + upper_bound − lower_bound, hoặc một mảng tần suất nếu khoảng cách bị chặn nhỏ, để giảm hệ số log.

Xây "cây centroid" (centroid tree) cho các bài truy vấn: lưu cha centroid par[c] của mỗi đỉnh. Cây này cao $O(\log N)$, dùng để leo lên cập nhật/truy vấn theo tổ tiên centroid.

int par[MAXN];   // cha trong cây centroid

void build(int root, int p) {
    get_size(root, -1);
    int c = get_centroid(root, -1, sz[root]);
    removed[c] = true;
    par[c] = p;                        // -1 nếu là gốc cây centroid
    for (auto [v, w] : adj[c])
        if (!removed[v])
            build(v, c);
}

Độ phức tạp

Bộ nhớ: $O(N)$ cho danh sách kề, mảng sz, removed, par. Nếu mỗi đỉnh centroid gắn một cấu trúc dữ liệu lưu thông tin của các đỉnh trong cây con của nó, tổng bộ nhớ là $O(N\log N)$ vì mỗi đỉnh thuộc $O(\log N)$ cây con centroid.

Lý do cốt lõi cho $\log N$: chiều cao cây centroid bị chặn bởi ${\log }_{2}N$ — sau mỗi lần phân rã, kích thước giảm ít nhất một nửa.

⚠️ Lỗi thường gặp

• Quên cập nhật sz sau khi xóa centroid. Phải gọi lại get_size cho mỗi cây con trước khi tìm centroid của nó; dùng sz cũ (của cây cha) sẽ tìm sai centroid và phá vỡ bất biến $\le N/2$, làm độ phức tạp bùng về $O(N^2)$.
• Đếm lặp đường đi trong cùng một nhánh. Nếu gom hết tất cả khoảng cách vào all rồi mới đếm, hai đỉnh cùng một nhánh sẽ bị ghép thành "đường đi qua centroid" sai (thực ra không qua centroid). Phải đếm nhánh hiện tại với all của các nhánh trước, rồi mới nạp vào all. (Cách khác: cộng tổng rồi trừ phần đếm lặp trong từng nhánh.)
• Tràn số (overflow). Số đường đi có thể tới $\left(\genfrac{}{}{0ex}{}{N}{2}\right)\approx 5\times {10}^9$ với $N={10}^5$ — vượt int. Dùng long long cho ans và cho tổng trọng số dist (trọng số lớn cộng dồn dễ tràn int).
• Đệ quy get_size/collect quá sâu gây tràn stack với cây hình đường thẳng ($N~{10}^5$). Lưu ý giới hạn stack; nếu cần, tăng stack hoặc viết DFS dạng vòng lặp. (Bản thân cây centroid chỉ sâu $O(\log N)$, nhưng DFS bên trong mỗi tầng vẫn có thể sâu tới size cây con.)
• Quên removed trong điều kiện duyệt. Mọi DFS (get_size, get_centroid, collect) đều phải bỏ qua đỉnh đã removed, nếu không sẽ "rò" sang phần cây đã xử lý ở tầng trên.
• Tính cả đường đi độ dài 0 (chính đỉnh với chính nó). Khởi tạo all = {0} để xử lý đường đi có centroid là một đầu mút, nhưng nhớ không đếm cặp $(c,c)$ làm đáp án dư nếu $K=0$.

Biến thể / Mở rộng

• Truy vấn động trên cây tĩnh: gắn lên mỗi đỉnh centroid một Fenwick/BIT chứa thông tin của cây con; khi cập nhật/truy vấn một đỉnh $u$, leo theo par trong cây centroid ($O(\log N)$ tổ tiên) và cộng dồn theo khoảng cách. Liên hệ: Fenwick Tree.
• Đếm cặp khoảng cách $\le k$: thay all.count(K-d) bằng đếm số phần tử $\le k-d$ (sort + upper_bound).
• Cây thay đổi cấu trúc (thêm/xóa cạnh) cần đường đi: centroid decomposition tĩnh không xử lý được trực tiếp, dùng Link-Cut Tree.

Bài tập luyện

• Âm và Dương (yinyang) — (Veteran) Đếm cặp đỉnh có đường đi "cân bằng" loại cạnh; bài nhập môn kinh điển: với mỗi centroid gom thông tin nhánh rồi ghép cặp.
• Bò Trốn (Platinum) (atlarge18) — (Expert) Tính đáp án cho mọi đỉnh gốc; luyện kết hợp centroid decomposition với suy luận trên cây và lá.
• Chuồng Trại Mới (newbarn) — (Expert) Thêm đỉnh động và truy vấn khoảng cách xa nhất; luyện gắn cấu trúc dữ liệu lên cây centroid và leo tổ tiên.
• Cây cân bằng (baltree) — (Master) Bài tổng hợp khó, kết hợp centroid decomposition với xử lý chuỗi trên đường đi.