树的重心分解简要模板

centroid-decomposition.cpp

struct centroid_decomposition {
    vector<int> size;
    vector<bool> used;
    vector<int> fa; // 重心树
    int n;
    const vector<vector<int>> &g; // vertices are 1-indexed

    int centroid, cmx; // cmx: size of max block after removing centroid
    void dfs(int u, int f, int n) { // 求重心
        size[u] = 1;
        int mx = 0;
        for (auto &v: g[u]) {
            if (v != f && !used[v]) {
                dfs(v, u, n);
                size[u] += size[v];
                Max(mx, size[v]);
            }
        }
        Max(mx, n - size[u]);
        if (mx < cmx) {
            centroid = u;
            cmx = mx;
        }
    }

    void divide(int u, int n, int c) { // c: 上次求出的重心
        cmx = INT_MAX;
        dfs(u, 0, n);
        fa[centroid] = c; // 构造重心树
        used[centroid] = true;
        // 慎用全局变量
        c = centroid;
        FOR(v, g[c]) { // 写成 FOR(v, g[centroid]) 也行，但是最好不要这样做！
            if (!used[v]) {
                int m = size[v] < size[c] ? size[v] : n - size[c]; // 这一步极容易错！
                divide(v, m, c);
            }
        }
    }

    centroid_decomposition(int n, const vector<vector<int>> &g) : n(n), g(g) {
        used.assign(n + 1, false);
        size.resize(n + 1);
        fa.resize(n + 1);
        divide(1, n, 0); //
    }
};