Centroid Decomposition

"Divide tree at centroid. Every path passes through O(log n) centroids."

Centroid decomposition recursively divides a tree at its centroid (node whose removal creates subtrees of size ≤ n/2). Any path between two nodes passes through O(log n) centroids in the decomposition tree. This enables O(n log n) or O(n log² n) solutions for: count pairs with path length k, nearest marked node on tree path, path queries that can't be handled by HLD.

16 min readgraph problems →

Problems you can solve with this pattern

3 problems · click any to start solving

All graph →

1Count Pairs Of NodesHardSolve

2Number of Good PathsHardSolve

3Distance Between Bus Stops (tree variant)MediumSolve

Centroid decomposition template

function centroidDecomposition(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

    const subSize = new Array(n).fill(0);
    const removed = new Array(n).fill(false);
    const centParent = new Array(n).fill(-1); // parent in centroid tree

    function getSize(u, p) {
        subSize[u] = 1;
        for (const v of adj[u]) if (!removed[v] && v !== p) subSize[u] += getSize(v, u);
        return subSize[u];
    }

    function getCentroid(u, p, treeSize) {
        for (const v of adj[u]) {
            if (!removed[v] && v !== p && subSize[v] > treeSize / 2) return getCentroid(v, u, treeSize);
        }
        return u;
    }

    function decompose(u, parent) {
        const sz = getSize(u, -1);
        const c = getCentroid(u, -1, sz);
        centParent[c] = parent;
        removed[c] = true;

        // Process all paths through c here:
        // For each v in adj[c] (not removed), collect distances from c into subtree
        // Then combine: answer for paths through c = merge info from different subtrees

        for (const v of adj[c]) if (!removed[v]) decompose(v, c);
        removed[c] = false; // restore for other uses (optional)
        return c; // return centroid tree root
    }

    return decompose(0, -1);
}

// Pattern for "count pairs with distance = k":
// At each centroid c:
//   1. Collect all distances from c to nodes in its component
//   2. Count pairs using two-pointer or hashmap: pairs where dist(c,u) + dist(c,v) = k
//   3. Subtract pairs where u and v are in same subtree (counted twice)

The centroid of a tree is a node whose removal leaves all subtrees of size ≤ n/2. Every tree has at least one centroid (findable in O(n)). Centroid decomposition builds a hierarchical decomposition: find centroid, process all paths through it, remove it, recurse on remaining subtrees. Since subtrees are ≤ half, depth is O(log n), so total processing is O(n log n) if per-centroid work is O(n).

Centroid decomposition template

function centroidDecomposition(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

    const subSize = new Array(n).fill(0);
    const removed = new Array(n).fill(false);
    const centParent = new Array(n).fill(-1); // parent in centroid tree

    function getSize(u, p) {
        subSize[u] = 1;
        for (const v of adj[u]) if (!removed[v] && v !== p) subSize[u] += getSize(v, u);
        return subSize[u];
    }

    function getCentroid(u, p, treeSize) {
        for (const v of adj[u]) {
            if (!removed[v] && v !== p && subSize[v] > treeSize / 2) return getCentroid(v, u, treeSize);
        }
        return u;
    }

    function decompose(u, parent) {
        const sz = getSize(u, -1);
        const c = getCentroid(u, -1, sz);
        centParent[c] = parent;
        removed[c] = true;

        // Process all paths through c here:
        // For each v in adj[c] (not removed), collect distances from c into subtree
        // Then combine: answer for paths through c = merge info from different subtrees

        for (const v of adj[c]) if (!removed[v]) decompose(v, c);
        removed[c] = false; // restore for other uses (optional)
        return c; // return centroid tree root
    }

    return decompose(0, -1);
}

// Pattern for "count pairs with distance = k":
// At each centroid c:
//   1. Collect all distances from c to nodes in its component
//   2. Count pairs using two-pointer or hashmap: pairs where dist(c,u) + dist(c,v) = k
//   3. Subtract pairs where u and v are in same subtree (counted twice)

Hard

Hard

Distance Between Bus Stops (tree variant)

Medium

Solve

Centroid decomposition invariant: Any path u→v in the tree passes through exactly one of their common centroid ancestors. Process all paths through centroid c: gather distances to all nodes in c's component, count/answer paths, subtract over-counting from same subtree.

Finding centroid: DFS to get subtree sizes. Centroid = node where max(subtree sizes, n - subtree size) ≤ n/2. Time: O(n).

vs HLD:
- HLD: path queries with segment tree, O(log²n) per query, supports updates
- Centroid decomp: path counting/existence queries, O(n log n) preprocessing

Common pattern: "Count pairs with path length = k" → at each centroid c, use a hashmap/sorted array to count pairs from different subtrees.

← Aho-Corasick Automaton Line Sweep →