Centroid Decomposition

ITrọng tâm

Vì sao phải chọn đỉnh “cân bằng”? Thử với một cây là đường thẳng. Nếu chọn $c$ là một đầu mút, bỏ nó đi thì mảnh còn lại vẫn gần đủ $n$ đỉnh; chia mãi, mỗi lần chỉ bớt một đỉnh, tổng công việc lại thành cỡ $n^2$. Nếu chọn đỉnh ở giữa, hai mảnh còn lại mỗi mảnh chỉ một nửa. Chia tiếp như vậy, sau khoảng $\log_2 n$ lần mỗi mảnh chỉ còn một đỉnh, giống như chặt nhị phân.

Trọng tâm là đỉnh mà khi bỏ đi, mảnh lớn nhất còn lại có không quá một nửa số đỉnh. Cây nào cũng có trọng tâm. Cách đi tìm: đứng ở một đỉnh bất kỳ; nếu có một mảnh lớn hơn một nửa thì bước sang phía mảnh đó. Phía sau lưng lúc này chưa tới một nửa nên không bao giờ phải quay lại, và mỗi bước đều tiến vào sâu hơn, nên cuối cùng sẽ dừng ở một đỉnh mà mọi mảnh đều không quá một nửa.

Trong hình, mỗi bước chọn trọng tâm của một mảnh (cam), bỏ nó đi rồi làm tiếp trên các mảnh còn lại. Nhãn là tầng:

Vì mảnh nhỏ đi ít nhất một nửa sau mỗi tầng, một đỉnh chỉ nằm trong khoảng $\log_2 n$ mảnh: với $2 \cdot 10^5$ đỉnh là chừng 18 mảnh. Ở mỗi tầng, tổng kích thước các mảnh không quá $n$. Nên nếu ở mỗi mảnh ta chỉ làm việc tỉ lệ với kích thước của nó, cả quá trình là $O(n \log n)$.

Tính trọng tâm thì treo mảnh ở một đỉnh rồi tính kích thước cây con như bài 3.1: BFS lấy thứ tự, đi ngược thứ tự để con xong trước cha. Bỏ đỉnh $u$ đi, các mảnh còn lại là cây con của từng con của $u$, cộng phần phía trên có (tổng số đỉnh trừ kích thước cây con của $u$) đỉnh. Ta chỉ cần mảnh lớn nhất trong số đó không quá một nửa.

Ví dụĐiểm Cân Bằng

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh. In một trọng tâm.

Lời giải. Tính kích thước mọi cây con khi treo cây ở một đỉnh bất kỳ. Bỏ đỉnh $u$ đi thì các phần còn lại là các cây con của con $u$, cùng phần “phía trên” có $n - sz_u$ đỉnh. $u$ là trọng tâm khi phần lớn nhất trong số đó không quá $n / 2$. Hàm centroid dưới đây được dùng lại nguyên vẹn ở mọi ví dụ sau, nên viết sẵn cho một thành phần bất kỳ chưa bị xóa.

Bước 1: kích thước không đệ quy. BFS từ s trên các đỉnh chưa bị xóa (del), ghi cha fa và thứ tự comp. Duyệt comp từ cuối lên thì mỗi đỉnh được cộng vào cha sau khi kích thước của nó đã đủ; mxc[p] là cây con lớn nhất của các con của p.

comp.assign(1, s);
fa[s] = 0;
for (int i = 0; i < (int)comp.size(); i++) {
    int u = comp[i];
    sz[u] = 1, mxc[u] = 0;
    for (int v : adj[u])
        if (!del[v] && v != fa[u]) fa[v] = u, comp.push_back(v);
}
for (int i = (int)comp.size() - 1; i > 0; i--) {
    int u = comp[i], p = fa[u];
    sz[p] += sz[u];
    mxc[p] = max(mxc[p], sz[u]);
}

Bước 2: kiểm điều kiện. max(mxc[u], tot - sz[u]) là phần lớn nhất còn lại khi bỏ $u$. Viết 2 * ... <= tot để khỏi chia.

int tot = comp.size();
for (int u : comp)
    if (2 * max(mxc[u], tot - sz[u]) <= tot) return u;

Trọng tâm luôn tồn tại, nên vòng trên chắc chắn trả về một đỉnh. Dòng return s cuối chỉ để hàm có giá trị trả về.

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

const int N = 2e5 + 5;
int n, fa[N], sz[N], mxc[N];
bool del[N];
vector<int> adj[N], comp;

int centroid(int s) {
    comp.assign(1, s);
    fa[s] = 0;
    for (int i = 0; i < (int)comp.size(); i++) {
        int u = comp[i];
        sz[u] = 1, mxc[u] = 0;
        for (int v : adj[u])
            if (!del[v] && v != fa[u]) fa[v] = u, comp.push_back(v);
    }
    for (int i = (int)comp.size() - 1; i > 0; i--) {
        int u = comp[i], p = fa[u];
        sz[p] += sz[u];
        mxc[p] = max(mxc[p], sz[u]);
    }
    int tot = comp.size();
    for (int u : comp)
        if (2 * max(mxc[u], tot - sz[u]) <= tot) return u;
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cout << centroid(1) << '\n';
}

ChạyInput7
1 2
2 3
3 4
4 5
4 6
6 7

Output4

IIĐường qua trọng tâm

Đứng ở trọng tâm $c$ của mảnh đang xét. Bỏ $c$ đi, mảnh vỡ thành vài nhánh. Một đường đi qua $c$ gồm hai nửa: một nửa đi xuống một nhánh, nửa kia đi xuống một nhánh khác, hoặc rỗng khi chính $c$ là một đầu.

Muốn đếm đường dài đúng $k$ qua $c$, ta ghép một nửa dài $d$ với một nửa dài $k - d$. Giữ mảng cnt[d]: số đỉnh đã gặp có khoảng cách tới $c$ đúng bằng $d$. Khởi đầu cnt[0] = 1, ứng với chính $c$ làm nửa rỗng.

Chỗ phải cẩn thận: hai nửa không được nằm cùng một nhánh. Hai đỉnh cùng nhánh thì đường thật giữa chúng không hề đi qua $c$; cộng hai khoảng cách tới $c$ lại sẽ đếm một đường không có thật. Cách tránh rất gọn: xử lý từng nhánh một, và với mỗi nhánh thì ghép trước, thêm sau. Mọi đỉnh của nhánh đang xét ghép với cnt (lúc này chỉ chứa các nhánh trước), xong mới cộng cả nhánh vào cnt. Như vậy hai nửa luôn thuộc hai nhánh khác nhau.

Xong $c$ thì đánh dấu $c$ đã xóa, dọn cnt (chỉ tới độ sâu đã dùng, không dọn cả mảng), rồi làm tiếp trên từng mảnh con. Thay vì đệ quy, giữ một ngăn xếp các đỉnh đại diện cho những mảnh còn phải xử lý.

Ví dụĐường Đi Đúng K Cạnh

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh, $k \le n$. Đếm số đường đi đơn có đúng $k$ cạnh.

Lời giải. Phân rã trọng tâm: tìm trọng tâm $c$ của mảnh, đếm mọi đường đi qua $c$, xóa $c$, rồi làm tiếp trên từng mảnh con. Đường qua $c$ có độ dài $k$ gồm một nửa độ sâu $d$ trong một nhánh và một nửa độ sâu $k - d$ ở nhánh khác, hoặc chính $c$ (độ sâu 0). centroid như ví dụ trước.

Bước 1: ngăn xếp thay đệ quy. st chứa các đỉnh đại diện cho mảnh cần xử lý. Lấy ra một đỉnh, tìm trọng tâm c của mảnh chứa nó và đánh dấu del[c]. cnt[0] = 1 là chính c: đường có một đầu là c ghép với nửa rỗng này.

int c = centroid(st.back());
st.pop_back();
del[c] = 1;
int maxd = 0;
cnt[0] = 1;

Bước 2: từng nhánh. BFS gom các đỉnh của nhánh vào q kèm độ sâu; đỉnh sâu hơn $k$ không ghép được với ai, nên không mở rộng đỉnh có dep == k. Vòng thứ nhất ghép với các nhánh trước; vòng thứ hai mới thêm nhánh này vào cnt.

for (int u : q) ans += cnt[k - dep[u]];
for (int u : q) cnt[dep[u]]++, maxd = max(maxd, dep[u]);

Bước 3: dọn và đẩy mảnh con. Xóa cnt chỉ tới maxd; xóa cả mảng mỗi lần sẽ tốn $O(n)$ cho mỗi trọng tâm, tức $O(n^2)$. Mỗi hàng xóm chưa bị xóa của c đại diện cho một mảnh con.

for (int d = 0; d <= maxd; d++) cnt[d] = 0;
for (int v : adj[c])
    if (!del[v]) st.push_back(v);

Cả bài $O(n \log n)$: mỗi đỉnh nằm trong khoảng $\log_2 n$ mảnh, và ở mỗi mảnh công việc tỉ lệ với kích thước của nó.

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

const int N = 2e5 + 5;
int n, k, fa[N], sz[N], mxc[N], dep[N], cnt[N];
bool del[N];
vector<int> adj[N], comp;

int centroid(int s) {
    comp.assign(1, s);
    fa[s] = 0;
    for (int i = 0; i < (int)comp.size(); i++) {
        int u = comp[i];
        sz[u] = 1, mxc[u] = 0;
        for (int v : adj[u])
            if (!del[v] && v != fa[u]) fa[v] = u, comp.push_back(v);
    }
    for (int i = (int)comp.size() - 1; i > 0; i--) {
        int u = comp[i], p = fa[u];
        sz[p] += sz[u];
        mxc[p] = max(mxc[p], sz[u]);
    }
    int tot = comp.size();
    for (int u : comp)
        if (2 * max(mxc[u], tot - sz[u]) <= tot) return u;
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ll ans = 0;
    vector<int> st = {1};
    while (!st.empty()) {
        int c = centroid(st.back());
        st.pop_back();
        del[c] = 1;
        int maxd = 0;
        cnt[0] = 1;
        for (int v : adj[c]) {
            if (del[v]) continue;
            vector<int> q = {v};
            fa[v] = c, dep[v] = 1;
            for (int i = 0; i < (int)q.size(); i++) {
                int u = q[i];
                if (dep[u] == k) continue;
                for (int w : adj[u])
                    if (!del[w] && w != fa[u]) fa[w] = u, dep[w] = dep[u] + 1, q.push_back(w);
            }
            for (int u : q) ans += cnt[k - dep[u]];
            for (int u : q) cnt[dep[u]]++, maxd = max(maxd, dep[u]);
        }
        for (int d = 0; d <= maxd; d++) cnt[d] = 0;
        for (int v : adj[c])
            if (!del[v]) st.push_back(v);
    }
    cout << ans << '\n';
}

ChạyInput6 3
1 2
2 3
2 4
4 5
4 6

Output4

IIIĐộ dài trong khoảng

Nếu đề hỏi số đường có độ dài nằm trong khoảng $[k_1, k_2]$ thì một nửa dài $d$ ghép được với cả một khoảng độ sâu, từ $k_1 - d$ tới $k_2 - d$. Lúc này cần hỏi tổng của cnt trên một đoạn, nên thay mảng đếm bằng Fenwick theo độ sâu (bài 1.7): mỗi lần ghép là một truy vấn đoạn $O(\log n)$, cả bài $O(n \log^2 n)$. Dọn Fenwick bằng cách trừ lại đúng những độ sâu đã thêm.

Khung này dùng được cho rất nhiều bài: thay “độ sâu” bằng tổng trọng số, tổng các số $\pm 1$, mặt nạ bit hay giá trị theo mô-đun; thay mảng đếm bằng Fenwick, map hay hai con trỏ trên danh sách đã sắp. Phần “ghép trước, thêm sau” thì giữ nguyên.

Ví dụĐường Đi Trong Khoảng Độ Dài

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh. Đếm số đường đi có số cạnh trong $[k_1, k_2]$.

Lời giải. Khung y như ví dụ trước. Khác ở chỗ nửa có độ sâu $d$ ghép được với mọi nửa có độ sâu trong $[k_1 - d, k_2 - d]$, nên mảng đếm thay bằng Fenwick theo độ sâu để hỏi tổng một đoạn. Đỉnh sâu hơn $k_2$ không cần duyệt.

Bước 1: Fenwick trên độ sâu. Độ sâu bắt đầu từ 0 nên chỉ số dời lên 1. get(i) là số nửa có độ sâu không quá $i$; i < 0 trả 0, i > n bị kẹp về $n$, nên gọi với cận bất kỳ cũng an toàn.

int get(int i) {
    if (i < 0) return 0;
    int s = 0;
    for (i = min(i, n) + 1; i; i -= i & -i) s += bit[i];
    return s;
}

Bước 2: đếm và thêm. Số nửa ở các nhánh trước có độ sâu trong $[k_1 - d, k_2 - d]$; used ghi lại mọi độ sâu đã thêm (kể cả độ sâu 0 của chính c).

for (int u : q) ans += get(k2 - dep[u]) - get(k1 - dep[u] - 1);
for (int u : q) add(dep[u], 1), used.push_back(dep[u]);

Bước 3: hoàn tác. Cuối mỗi trọng tâm trừ lại đúng những ô đã thêm; Fenwick trở về toàn 0 mà không tốn $O(n)$.

for (int d : used) add(d, -1);

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

const int N = 2e5 + 5;
int n, k1, k2, fa[N], sz[N], mxc[N], dep[N], bit[N];
bool del[N];
vector<int> adj[N], comp;

void add(int i, int v) {
    for (i++; i <= n + 1; i += i & -i) bit[i] += v;
}

int get(int i) {
    if (i < 0) return 0;
    int s = 0;
    for (i = min(i, n) + 1; i; i -= i & -i) s += bit[i];
    return s;
}

int centroid(int s) {
    comp.assign(1, s);
    fa[s] = 0;
    for (int i = 0; i < (int)comp.size(); i++) {
        int u = comp[i];
        sz[u] = 1, mxc[u] = 0;
        for (int v : adj[u])
            if (!del[v] && v != fa[u]) fa[v] = u, comp.push_back(v);
    }
    for (int i = (int)comp.size() - 1; i > 0; i--) {
        int u = comp[i], p = fa[u];
        sz[p] += sz[u];
        mxc[p] = max(mxc[p], sz[u]);
    }
    int tot = comp.size();
    for (int u : comp)
        if (2 * max(mxc[u], tot - sz[u]) <= tot) return u;
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k1 >> k2;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ll ans = 0;
    vector<int> st = {1};
    while (!st.empty()) {
        int c = centroid(st.back());
        st.pop_back();
        del[c] = 1;
        vector<int> used = {0};
        add(0, 1);
        for (int v : adj[c]) {
            if (del[v]) continue;
            vector<int> q = {v};
            fa[v] = c, dep[v] = 1;
            for (int i = 0; i < (int)q.size(); i++) {
                int u = q[i];
                if (dep[u] == k2) continue;
                for (int w : adj[u])
                    if (!del[w] && w != fa[u]) fa[w] = u, dep[w] = dep[u] + 1, q.push_back(w);
            }
            for (int u : q) ans += get(k2 - dep[u]) - get(k1 - dep[u] - 1);
            for (int u : q) add(dep[u], 1), used.push_back(dep[u]);
        }
        for (int d : used) add(d, -1);
        for (int v : adj[c])
            if (!del[v]) st.push_back(v);
    }
    cout << ans << '\n';
}

ChạyInput7 2 3
1 2
2 3
2 4
4 5
4 6
6 7

Output13

IVCây trọng tâm

Mỗi khi chọn được một trọng tâm, ghi lại trọng tâm của mảnh vừa chứa nó, gọi là cha của nó. Nối các trọng tâm theo quan hệ cha con ấy, ta được một cây mới: cây trọng tâm. Cây này chỉ sâu khoảng $\log_2 n$ tầng, dù cây gốc có thể là một đường dài.

Cây trọng tâm có một tính chất rất đắt giá. Lấy hai đỉnh $u$, $v$ bất kỳ, và nhìn trọng tâm đầu tiên tách chúng ra hai mảnh khác nhau. Đường từ $u$ tới $v$ đi qua đúng trọng tâm đó, và nó là một tổ tiên chung của $u$ và $v$ trên cây trọng tâm. Các tổ tiên chung khác cũng cho một con số $\operatorname{dist}(u, c) + \operatorname{dist}(c, v)$, nhưng con số ấy không bao giờ nhỏ hơn khoảng cách thật. Vậy

Nhờ đó, mỗi đỉnh chỉ cần nhớ khoảng cách tới khoảng $\log n$ trọng tâm tổ tiên của nó. Khi dựng, BFS từ mỗi trọng tâm $c$ trong mảnh của nó và lưu dist[lev[c]][u]. Với bài “đỉnh đánh dấu gần nhất”: đánh dấu $v$ thì đi lên mọi tổ tiên $c$ của $v$ (kể cả $v$), cập nhật best[c] là khoảng cách nhỏ nhất từ $c$ tới một đỉnh đánh dấu; hỏi $v$ thì lấy nhỏ nhất của best[c] + dist(v, c) trên các tổ tiên. Mỗi thao tác chỉ đi qua khoảng $\log n$ trọng tâm.

Ví dụTín Hiệu Đỏ Gần Nhất

Đề. Cây $n \le 10^5$ đỉnh, ban đầu chỉ đỉnh 1 đỏ. $m \le 10^5$ thao tác: tô đỏ một đỉnh; hỏi khoảng cách từ một đỉnh tới đỉnh đỏ gần nhất.

Lời giải. Dựng cây trọng tâm một lần. Mỗi trọng tâm $c$ ở tầng $L$ BFS trong mảnh của nó và ghi dist[L][u], khoảng cách từ $u$ tới $c$. Mỗi đỉnh có tối đa $\log_2 n + 1$ trọng tâm tổ tiên, nên bảng có $O(n \log n)$ ô. best[c] là khoảng cách nhỏ nhất từ $c$ tới một đỉnh đỏ nằm trong mảnh của $c$. Tô đỏ và hỏi đều chỉ đi trên các trọng tâm tổ tiên của đỉnh.

Bước 1: dựng cây trọng tâm. Ngăn xếp giữ bộ ba (đỉnh đại diện, trọng tâm cha, tầng). Lấy ra thì tìm trọng tâm c, ghi cpar[c], lev[c], đánh dấu del[c], rồi BFS từ c trên phần chưa bị xóa để điền dist[L]. Các hàng xóm còn sống đi vào ngăn xếp với tầng $L + 1$. Một đỉnh $u$ được BFS ở mọi tầng mà nó còn nằm trong mảnh, nên dist[lev[c]][u] có nghĩa cho đúng các trọng tâm tổ tiên của $u$.

int c = centroid(cur[0]), L = cur[2];
cpar[c] = cur[1], lev[c] = L, del[c] = 1;
vector<int> q = {c};
fa[c] = 0, dist[L][c] = 0;
for (int i = 0; i < (int)q.size(); i++) {
    int u = q[i];
    for (int w : adj[u])
        if (!del[w] && w != fa[u]) fa[w] = u, dist[L][w] = dist[L][u] + 1, q.push_back(w);
}
for (int v : adj[c])
    if (!del[v]) st.push_back({v, c, L + 1});

Bước 2: tô đỏ và hỏi. Đi từ $v$ lên theo cpar, kể cả chính $v$ ($v$ cũng là trọng tâm của một mảnh nào đó).

void paint(int v) {
    for (int c = v; c; c = cpar[c]) best[c] = min(best[c], dist[lev[c]][v]);
}

int ask(int v) {
    int res = INF;
    for (int c = v; c; c = cpar[c]) res = min(res, best[c] + dist[lev[c]][v]);
    return res;
}

Vì sao ask đúng: đường từ $v$ tới đỉnh đỏ gần nhất $w$ đi qua trọng tâm đầu tiên tách $v$ và $w$; trọng tâm ấy nằm trên đường lên của $v$, và best ở đó đã tính tới $w$. Các trọng tâm khác chỉ cho giá trị không nhỏ hơn khoảng cách thật. INF = 1e9 cộng khoảng cách tới $10^5$ vẫn vừa int; đỉnh 1 đỏ sẵn nên gọi paint(1) trước.

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

const int N = 1e5 + 5, LG = 18, INF = 1e9;
int n, m, fa[N], sz[N], mxc[N], cpar[N], lev[N], best[N], dist[LG][N];
bool del[N];
vector<int> adj[N], comp;

int centroid(int s) {
    comp.assign(1, s);
    fa[s] = 0;
    for (int i = 0; i < (int)comp.size(); i++) {
        int u = comp[i];
        sz[u] = 1, mxc[u] = 0;
        for (int v : adj[u])
            if (!del[v] && v != fa[u]) fa[v] = u, comp.push_back(v);
    }
    for (int i = (int)comp.size() - 1; i > 0; i--) {
        int u = comp[i], p = fa[u];
        sz[p] += sz[u];
        mxc[p] = max(mxc[p], sz[u]);
    }
    int tot = comp.size();
    for (int u : comp)
        if (2 * max(mxc[u], tot - sz[u]) <= tot) return u;
    return s;
}

void paint(int v) {
    for (int c = v; c; c = cpar[c]) best[c] = min(best[c], dist[lev[c]][v]);
}

int ask(int v) {
    int res = INF;
    for (int c = v; c; c = cpar[c]) res = min(res, best[c] + dist[lev[c]][v]);
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<array<int, 3>> st = {{1, 0, 0}};
    while (!st.empty()) {
        array<int, 3> cur = st.back();
        st.pop_back();
        int c = centroid(cur[0]), L = cur[2];
        cpar[c] = cur[1], lev[c] = L, del[c] = 1;
        vector<int> q = {c};
        fa[c] = 0, dist[L][c] = 0;
        for (int i = 0; i < (int)q.size(); i++) {
            int u = q[i];
            for (int w : adj[u])
                if (!del[w] && w != fa[u]) fa[w] = u, dist[L][w] = dist[L][u] + 1, q.push_back(w);
        }
        for (int v : adj[c])
            if (!del[v]) st.push_back({v, c, L + 1});
    }
    for (int v = 1; v <= n; v++) best[v] = INF;
    paint(1);
    while (m--) {
        int t, v;
        cin >> t >> v;
        if (t == 1) paint(v);
        else cout << ask(v) << '\n';
    }
}

+13 dòngChạyInput6 7
1 2
2 3
2 4
4 5
4 6
2 5
1 4
2 5
2 3
1 3
2 6
2 3

Output3
1
2
1
0

Dựng $O(n \log n)$, mỗi thao tác $O(\log n)$. Mỗi thao tác đọc dist của đúng một đỉnh qua khoảng 18 tầng, nên cách xếp bảng ảnh hưởng tới tốc độ:

Xếp theo đỉnh (dist[u][L], 18 số của một đỉnh nằm liền nhau) nhanh hơn xếp theo tầng (dist[L][u]) khoảng 1,7 lần, vì một lần đọc bộ nhớ đệm đủ cho cả đường lên. Quy tắc: dữ liệu một truy vấn đọc cùng lúc thì để sát nhau.