Centroid Decomposition

Divide-and-conquer on trees via centroid selection for O(n log n) path processing.

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#centroid#decomposition#tree#divide-and-conquer

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int sz[MAXN];
bool removed[MAXN];

int getSize(int u, int p) {
    sz[u] = 1;
    for (int v : adj[u])
        if (v != p && !removed[v])
            sz[u] += getSize(v, u);
    return sz[u];
}

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

void decompose(int u) {
    int c = getCentroid(u, -1, getSize(u, -1));
    removed[c] = true;

    // process all paths through centroid c here

    for (int v : adj[c])
        if (!removed[v]) decompose(v);
}

32 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Centroid Decomposition

Recursively split a tree at its centroid — a node whose largest subtree has $\le n/2$ nodes. The resulting decomposition tree has height $O(\log n)$ .

How It Works

Compute subtree sizes for the current component

Find the centroid by walking toward the heavy child (

\text{sz}[v] \cdot 2 > \text{total}

)

Process all paths through the centroid

Mark centroid as removed, recurse on each remaining subtree

When to Use

Counting/finding paths with a specific property (length, weight, XOR, etc.)

Distance queries from every node to a set of special nodes

Turning

O(n^2)

tree brute-force into

O(n \log n)

Notes

decompose() is a skeleton — add your path-processing logic after finding the centroid

Each node appears in

O(\log n)

centroid subproblems

Complexity

Time —

O(n \log n)

Space —

O(n)