← all categories

Centroid Decomposition de137c00

Centroid decomposition solving "min #edges among paths of length exactly targetLen" (IOI Race). Shows the general pattern (subtree size -> find centroid -> combine paths through the centroid, one child branch at a time so two halves from the same subtree never combine -> recurse on the remaining pieces); adapt solve()'s merge step for a different centroid problem, subtreeSize()/findCentroid() never need to change.

Time: O(n \log n). tested

content/graphs/centroid-decomposition.h

struct CentroidDecomp {
    int n;
    ll targetLen;
    vector<vector<pair<int, ll>>> adj;
    vector<bool> alive;
    vector<int> sz;

    CentroidDecomp(int n, ll targetLen, vector<vector<pair<int, ll>>> &adj)
        : n(n), targetLen(targetLen), adj(adj), alive(n, true), sz(n) {}

    int subtreeSize(int u, int p) {
        sz[u] = 1;
        for (auto &[v, w] : adj[u])
            if (v != p && alive[v]) sz[u] += subtreeSize(v, u);
        return sz[u];
    }

    int findCentroid(int target, int u, int p) {
        for (auto &[v, w] : adj[u])
            if (v != p && alive[v] && 2 * sz[v] > target) return findCentroid(target, v, u);
        return u;
    }

    void collect(vector<pair<ll, int>> &out, ll dist, int edges, int u, int p) {
        if (dist > targetLen) return;
        out.push_back({dist, edges});
        for (auto &[v, w] : adj[u])
            if (v != p && alive[v]) collect(out, dist + w, edges + 1, v, u);
    }

    int solve(int u) {
        subtreeSize(u, -1);
        int cen = findCentroid(sz[u], u, -1);
        alive[cen] = false;

        int res = INT_MAX;
        unordered_map<ll, int> best;
        best[0] = 0;
        for (auto &[v, w] : adj[cen]) {
            if (!alive[v]) continue;
            vector<pair<ll, int>> branch;
            collect(branch, w, 1, v, cen);
            for (auto &[d, c] : branch)
                if (targetLen - d >= 0 && best.count(targetLen - d)) res = min(res, best[targetLen - d] + c);
            for (auto &[d, c] : branch) {
                auto it = best.find(d);
                if (it == best.end() || it->second > c) best[d] = c;
            }
        }

        for (auto &[v, w] : adj[cen]) if (alive[v]) res = min(res, solve(v));
        return res;
    }
};