Centroid Decomposition

Recursively split a tree at its centroid, building a centroid tree of depth $O(\log n)$. It is the standard tool for counting or optimising over all paths in a tree.

The centroid

A vertex whose removal leaves every component of size $\le n/2$. Every tree has one or two, found in one pass over the subtree sizes:

int findCentroid(int v, int p, int total) {
    for (int c : adj[v])
        if (c != p && !removed[c] && sz[c] > total / 2)
            return findCentroid(c, v, total);
    return v;
}

The decomposition

void decompose(int v, int parentCentroid) {
    computeSizes(v, -1);
    int c = findCentroid(v, -1, sz[v]);
    removed[c] = true;
    cpar[c] = parentCentroid;
 
    solve(c);                                   // handle all paths THROUGH c
 
    for (int u : adj[c])
        if (!removed[u]) decompose(u, c);
}

Each level halves the component sizes, so the centroid tree has depth $O(\log n)$ and the total work across all levels is $O(n\log n)$ (each vertex appears in $O(\log n)$ components).

Why it works for path problems

Every path in the tree passes through exactly one highest centroid in the decomposition — the first centroid removed that lies on it. So if solve(c) correctly counts all paths through $c$ within the current component, summing over all centroids counts every path exactly once, with no double counting.

The template for solve

void solve(int c) {
    // 1. collect (depth, other data) for every vertex in the component, per branch
    // 2. count valid pairs across ALL vertices (this over-counts pairs in the same branch)
    // 3. for each branch, count valid pairs WITHIN it and subtract
}

The “count everything, then subtract per branch” pattern avoids the $O({\text{branches}}^2)$ pairing and is the standard way to write it.

Alternatively, process branches one at a time, querying against an accumulator of all previous branches — no subtraction needed, and often cleaner:

map<int,int> seen; seen[0] = 1;                 // the centroid itself
for (int u : adj[c]) {
    if (removed[u]) continue;
    vector<int> cur; collect(u, c, 1, cur);
    for (int d : cur) ans += seen.count(K - d) ? seen[K - d] : 0;   // query first
    for (int d : cur) seen[d]++;                                    // then insert
}

What it solves

Problem	Per-centroid work
Count paths of length exactly $K$	count depth pairs summing to $K$
Count paths of length $\le K$	sort depths, two pointers
Count paths with XOR $=K$	hash map of prefix XORs
Closest marked vertex to each query	store distances to ancestors in the centroid tree
Add $x$ to all vertices within distance $d$	update along centroid ancestors
Count paths with at most $k$ “bad” edges	2D counting with a BIT
Distance-limited queries with updates	the centroid tree as an index

The centroid-tree-as-index technique

For each vertex $v$, store its distance to each of its $O(\log n)$ centroid ancestors. Then:

• Update ($v$ becomes marked): walk up the centroid tree, updating each ancestor’s stored minimum with dist(v, ancestor).
• Query (nearest marked to $u$): walk up, taking $\min$ over dist(u, ancestor) + best[ancestor].

Both $O(\log n)$ (plus the cost of the distance query). This solves the classic “paint a vertex / find the nearest painted vertex” problem, and it is the main reason to build the centroid tree explicitly rather than just recursing.

Distances to centroid ancestors are precomputed during the decomposition, or answered with LCA in $O(\log n)$.

Complexity

• Build: $O(n\log n)$
• Memory: $O(n\log n)$ if you store all vertex-to-centroid-ancestor distances, $O(n)$ otherwise
• Per query/update using the centroid tree: $O(\log n)$ or $O({\log }^{2}n)$

Centroid vs heavy-light

	Centroid decomposition	HLD
Splits by	subtree size (vertices)	heavy paths (edges)
Structure	a tree of depth $O(\log n)$	$O(\log n)$ chains per root-leaf path
Good for	counting over all paths, distance queries	path updates and queries between two given vertices
Typical query	”how many pairs at distance $K$"	"sum along the path $u\to v$”

They solve different problems and are not interchangeable.

See also: HLD · Tree Fundamentals · DSU on Tree