Centroid Decomposition

Prerequisites: DFS, divide and conquer, trees.

Centroid decomposition is a divide-and-conquer technique on trees. It helps with path problems: counting paths with a property, distances, queries on tree paths, and dynamic updates with O(log N) depth.

This lesson follows CP-Algorithms — Centroid Decomposition.

The idea

Recursively pick a centroid — a vertex whose removal splits the tree into components each of size at most N/2. That guarantees O(log N) recursion depth.

At each level:

1. Find the centroid of the current component
2. Process all paths that pass through this centroid
3. Remove the centroid (mark used)
4. Recurse on each remaining subtree

Every original tree path crosses the centroid of some component exactly once when that centroid is processed — that is why the technique works.

What is a centroid?

A centroid of a tree with N vertices is a node whose removal leaves no subtree with more than ⌊N/2⌋ vertices.

• Every tree has at least one and at most two centroids.
• If there are two, they are adjacent.

Properties

Property	Statement
Decomposition depth	O(log N) — each step at least halves the component
Path coverage	Every path in the tree passes through some centroid during decomposition
Per-vertex work	Each vertex appears in O(log N) levels → often O(N log N) total

Finding a centroid — O(N)

1. DFS to compute subtree sizes in the current component (skip removed nodes).
2. Start at any vertex v.
3. If some child u has subtree_size[u] > N/2, move to u and repeat.
4. If no such child exists, v is a centroid.

int get_subtree_size(int v, int p = -1) {
    subtree_size[v] = 1;
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        subtree_size[v] += get_subtree_size(u, v);
    }
    return subtree_size[v];
}

int get_centroid(int v, int tree_size, int p = -1) {
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        if (subtree_size[u] * 2 > tree_size)
            return get_centroid(u, tree_size, v);
    }
    return v;
}

🧪 Find the centroid of a small tree

Check: centroids

Quiz

Centroid definition

1 / 4

A centroid of an N-node tree satisfies…

Pick an answer to see if you are right.

Interactive walkthrough

Step through centroid finding and recursive decomposition on a 5-node example (centroid 3).

Algorithm template

Example: count paths of exactly K edges (distinct endpoints).

For each centroid, count pairs in different child subtrees whose distances to the centroid sum to K:

• DFS each child subtree for distances from the centroid (cap at K).
• When processing child u, add pairs (d, K−d) against distances seen in previous children.
• Then merge u's distances into the global map.

void process_centroid(int centroid) {
    unordered_map<int, int> all_distances;
    all_distances[0] = 1;  // centroid to itself

    for (int u : adj[centroid]) {
        if (removed[u]) continue;

        vector<int> current_distances;
        get_distances(u, centroid, 1, current_distances);

        for (int d : current_distances) {
            if (K - d >= 0)
                answer += all_distances[K - d];
        }
        for (int d : current_distances)
            all_distances[d]++;
    }
}

void decompose(int v) {
    int tree_size = get_subtree_size(v);
    int centroid = get_centroid(v, tree_size);

    process_centroid(centroid);
    removed[centroid] = true;

    for (int u : adj[centroid])
        if (!removed[u])
            decompose(u);
}

Adapt process_centroid for XOR sums, length ranges, prime distances, etc.

Building the centroid tree

If you need explicit centroid-tree structure (queries, LCA on centroids):

int centroid_parent[MAXN];

int decompose(int v, int p = -1) {
    int tree_size = get_subtree_size(v);
    int centroid = get_centroid(v, tree_size);

    centroid_parent[centroid] = p;
    removed[centroid] = true;

    for (int u : adj[centroid])
        if (!removed[u])
            decompose(u, centroid);

    return centroid;
}

Each node's parent is the centroid found in the larger component that contained it. Height is O(log N).

Check: path processing

Quiz

Path coverage

1 / 4

Why process paths at each centroid separately?

Pick an answer to see if you are right.

Practice drills

Activity: Subtree size

Tree with n nodes (1-indexed), n-1 edges. Return subtree size of node 1 when rooted at 1. Input: n, then edges.

Contest problems

Finding a Centroid

Judge: CSES — Finding a Centroid

Find any centroid of an n-node tree (n ≤ 2·10⁵).

Why this lesson?

Direct application of DFS sizes + walk-to-heavy-child.

Sample

Input
5
1 2
2 3
3 4
3 5

Output
3

When to reach for centroid decomposition

Signal	Technique
Count/query paths in a tree	Decompose + process at centroids
“Every path considered once”	Path coverage property
Dynamic nearest special node	Centroid tree + per-ancestor data
Need O(N log N) on tree paths	Often centroid + map/BIT per level

Previous: Bit Manipulation · Binary Search

Source: CP-Algorithms — Centroid Decomposition