guest@itl:~/home/graph$
templates/centroid-decomposition.cpp
compilable
$cat templates/centroid-decomposition

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
Log in to track progress, save custom versions, and organize into collections.Log In
$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 ≤n/2\le n/2 nodes. The resulting decomposition tree has height O(log⁡n)O(\log n).

How It Works

  • Compute subtree sizes for the current component

  • Find the centroid by walking toward the heavy child (sz[v]⋅2>total\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(n2)O(n^2) tree brute-force into O(nlog⁡n)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)O(\log n) centroid subproblems

    • Complexity

  • Time — O(nlog⁡n)O(n \log n)

  • Space — O(n)O(n)