Centroid Decomposition

Trọng tâm

Trọng tâm là đỉnh mà khi bỏ đi, mọi thành phần còn lại có không quá $\lfloor n/2 \rfloor$ đỉnh. Luôn tồn tại: bắt đầu từ một đỉnh bất kỳ, nếu có nhánh lớn hơn một nửa thì bước sang nhánh đó; nhánh phía sau lưng chỉ còn chưa tới một nửa nên không bao giờ quay lại, và quá trình dừng.

Cài đặt: BFS lấy thứ tự và cha, duyệt ngược để tính sz và mxc (cây con lớn nhất). Phần lớn nhất khi bỏ $u$ là $\max(mxc_u, n - sz_u)$; đỉnh đầu tiên có giá trị này không quá $n/2$ là trọng tâm. Dùng BFS thay DFS để cây dạng đường dài không làm tràn ngăn xếp.

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

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: bắt đầu ở gốc và đi sang con có cây con lớn hơn $tot / 2$ chừng nào còn con như vậy; mỗi bước phần phía trên vẫn nhỏ hơn $tot / 2$, và quá trình dừng ở một đỉnh thỏa điều kiện. 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

Mỗi lần gọi $O(tot)$.

Đường qua trọng tâm

Ở trọng tâm $c$ của thành phần hiện tại, mỗi đường đi qua $c$ ghép từ hai nửa thuộc hai nhánh khác nhau (hoặc một nửa rỗng, tức $c$ là một đầu). Duyệt các nhánh lần lượt: với nhánh hiện tại, tính độ sâu mọi đỉnh tới $c$, ghép với mảng đếm cnt[d] của các nhánh trước (khởi đầu cnt[0] = 1 cho chính $c$), rồi mới thêm nhánh này vào cnt. Ghép trước, thêm sau thì hai nửa không bao giờ cùng một nhánh, nên không đếm đường không đơn.

Xong $c$ thì đánh dấu $c$ đã xóa, xóa mảng đếm (chỉ tới độ sâu đã dùng), rồi xử lý từng thành phần con. Mỗi tầng tốn tổng $O(n)$, có $O(\log n)$ tầng. Dùng ngăn xếp các đỉnh đại diện thành phần thay cho đệ quy.

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 thành phần, đếm mọi đường đi qua $c$, xóa $c$, rồi làm tiếp trên từng thành phần 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 thành phần cần xử lý. Lấy ra một đỉnh, tìm trọng tâm c của thành phần 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. Tách hai vòng như vậy thì hai đầu của một đường không bao giờ cùng một nhánh.

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 thành phần 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 thành phần con.

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

Vì sao $O(n \log n)$: mỗi thành phần con có không quá một nửa số đỉnh của thành phần cha, nên mỗi đỉnh nằm trong tối đa $\log_2 n$ thành phần, và ở mỗi thành phần công việc tuyến tính theo kích thước.

#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

$O(n \log n)$.

Độ dài trong khoảng

Cần đếm các cặp có tổng độ sâu trong $[k_1, k_2]$: với nửa có độ sâu $d$, số nửa còn lại phù hợp là tổng cnt trên đoạn $[k_1 - d, k_2 - d]$. Thay mảng đếm bằng Fenwick theo độ sâu, mỗi lần ghép một truy vấn đoạn $O(\log n)$, tổng $O(n \log^2 n)$. Xóa Fenwick bằng cách trừ lại đúng các độ sâu đã thêm.

Cùng khung này đổi “độ sâu” thành tổng trọng số, tổng $\pm 1$, mặt nạ bit, giá trị theo mô-đun; cấu trúc ghép đổi thành mảng, Fenwick, map hay hai con trỏ trên danh sách đã sắp.

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

Mỗi đỉnh của mỗi thành phần tốn thêm một truy vấn và một cập nhật Fenwick: $O(n \log^2 n)$.

Cây trọng tâm

Ghi lại trọng tâm cha cpar[c] (trọng tâm của thành phần vừa chứa $c$) được cây trọng tâm độ sâu $O(\log n)$. Với mọi $u, v$, đường $u \to v$ đi qua trọng tâm tổ tiên chung thấp nhất $c$ của chúng trong cây trọng tâm, nên

Khi dựng, BFS từ mỗi trọng tâm $c$ trong thành phần của nó và lưu dist[lev[c]][u]; mỗi đỉnh có tối đa $\log n$ giá trị như vậy. Đánh dấu $v$: với 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$: lấy nhỏ nhất của best[c] + dist(v, c) trên các tổ tiên. Mỗi thao tác $O(\log n)$.

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 thành phần 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 thành phần 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 thành phần, 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 thành phần 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 tổ tiên chung thấp nhất $c$ của $v$ và $w$; $c$ nằm trên đường lên của $v$, và best[c] đã 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 2 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.