---
title: "Centroid Decomposition"
summary: The divide-and-conquer that turns "count pairs at distance d" into O(n log n) — plus the centroid itself, proved, and the traps that make implementations slow.
difficulty: hard
tags: [trees, divide and conquer, paths]
time: n log n
space: n log n
prereq: [trees/diameter]
see: [advanced-tree/small-to-large]
demo: centroid
---

:::definition label="Centroid tree"
Recursively: find the centroid $c$ of the current component, record it, delete it, and recurse on the remaining components. Making each component's centroid the parent of the other components' centroids gives the **centroid tree** on the same $n$ vertices, of depth $\le \log_2 n$.
:::

:::theorem title="Depth O(log n), construction O(n log n)"
Every root-to-leaf path in the centroid tree has length $\le \log_2 n + 1$, and the total work is $O(n\log n)$ if each level's component sizes are summed over that level (each vertex participates in $\le \log n$ levels, and finding a centroid within a component costs time linear in its size).
:::

:::proof
By the centroid property, the component containing any vertex $v$ after removing its centroid has size $\le$ half of the current component. So along a centroid-tree root-to-leaf path the component sizes decrease geometrically, giving $\le \log_2 n$ levels, and each vertex is "worked on" once per level it appears in. ∎
:::

```cpp centroid-decomp.cpp
int sub[n], dead[n]{}, par_in_ctree[n];

int subtree_sizes(int v, int p, int total, int &best_mx, int &best) {
    sub[v] = 1; int mx = 0;
    for (int to : g[v]) if (to != p && !dead[to]) {
        int s = subtree_sizes(to, v, total, best_mx, best);
        mx = max(mx, s); sub[v] += s;
    }
    mx = max(mx, total - sub[v]);                 // the "upward" part
    if (mx < best_mx) { best_mx = mx; best = v; } // first strict improvement
    return sub[v];
}

int find_centroid(int entry, int total) {
    int best_mx = n + 1, best = entry;
    subtree_sizes(entry, -1, total, best_mx, best);
    return best;
}

int count_component(int v, int p) {               // size of v's live component
    int s = 1;
    for (int to : g[v]) if (to != p && !dead[to]) s += count_component(to, v);
    return s;
}

void build(int entry, int parent) {
    int total = count_component(entry, -1);
    int c = find_centroid(entry, total);
    par_in_ctree[c] = parent;
    dead[c] = 1;                                  // "delete" it
    for (int to : g[c]) if (!dead[to]) build(to, c);
}
```


:::note title="Iterate, don't recurse blindly"
`build` recurses $\le \log n$ deep, so it is safe; the *inner* `sz` DFS is $O(\text{component})$ deep — on a path of $10^6$ vertices that is a stack overflow. Either make the size DFS iterative, or keep the habit of stating $n \le 2\cdot 10^5$ and adding `ulimit -s unlimited` to the harness (@foundations/walks).
:::

## The counting pattern
:::idea
Every pair $(u,v)$ has a unique **highest** centroid-tree node $c$ that separates them — the first centroid whose removal puts $u$ and $v$ in different components (or equals one of them). So "count pairs satisfying a distance property" decomposes as: at each centroid, count pairs *through* it, subtract pairs that actually lie inside one child component (they belong to a lower level).
:::

```cpp count-pairs-distance.cpp
long long ans = 0; int freq[2 * K + 1]{};         // freq[d] = #vertices at distance d so far
int sub[n], dead[n], dist_tmp[n];

void collect(int v, int p, int d, vector<int> &out) {
    out.push_back(d);
    for (int to : g[v]) if (to != p && !dead[to]) collect(to, v, d + w(v, to), out);
}

void solve(int entry) {
    int total = count_component(entry, -1);
    int c = find_centroid(entry, total);
    dead[c] = 1;

    vector<int> all{ 0 };                           // {0} = the centroid itself
    freq[0]++;
    for (int to : g[c]) {
        if (dead[to]) continue;
        vector<int> ds; collect(to, c, w(c, to), ds);
        for (int d : ds) if (K - d >= 0) ans += freq[K - d];   // pairs through c only
        for (int d : ds) { freq[d]++; all.push_back(d); }     // then absorb this child
    }
    for (int d : all) freq[d]--;                                  // leave the array clean

    for (int to : g[c]) if (!dead[to]) solve(to);
}
```
Each unordered pair $(u,v)$ is counted exactly once: at the first centroid whose removal separates them, where `dist(u,c) + dist(v,c) = dist(u,v)` holds.


:::props title="What the level data must support"
- **count pairs at distance exactly / at most K** → a frequency array or sort+two-pointers over `all` (each level $O(\text{size})$, total $O(n \log n)$),
- **count pairs with $\operatorname{dist} \in [L,R]$** → prefix sums of the same frequency array, two queries per pair,
- **coloured pairs / "path contains colour X"** → per-level map from colour to count, merged as in @advanced-tree/small-to-large,
- **nearest marked vertex** (dynamic!) → keep at each vertex its $\le \log n$ centroid ancestors, each with a multiset of distances to marked vertices in its component: point update $O(\log^2 n)$, query $O(\log^2 n)$ — this is the intended solution of CSES-style "dynamic distance to a special node" and CF 342E *Xenia and Tree*,
- **path diameter of a set under updates** → same ancestor table, $\max$ instead of multiset,
- **"is there a cycle of length K with a chord"**-style tree problems reduce to the pair count above.
:::

:::warning title="The three classic bugs"
1. **Recounting**: forgetting that a pair inside one child is handled at a *lower* level, so counting it at both ⇒ over-count. The fix is the "subtract within-child pairs" formulation, or (cleaner) accumulate `all` only from *previous* children as above.
2. **Reusing the frequency array** across centroids without clearing the touched entries only — a full `fill` per level is $O(n)$ per level only if sized by component; on $10^6$ this is fine, but on many test cases it becomes $O(T n)$; use a touched-list.
3. **Distance measured in the original tree vs. in the component**: paths through $c$ are shortest paths in $T$ (unique path), so $\operatorname{dist}_T(u,v) = \operatorname{dist}(u,c) + \operatorname{dist}(v,c)$ *only when the $u$–$v$ path goes through $c$* — which is exactly the separated case. For same-child pairs this identity is false, which is another reason they must not be counted at this level.
:::

:::demo id="centroid" caption="Watch the recursion: the component shrinks by at least half at every level, so the highlight sequence is geometric. The centroid is not the root, and moving the root does not move the centroid."
:::

:::note title="Centroid vs. HLD, once"
HLD splits a path into $O(\log n)$ **contiguous** pieces (so a segment tree can work); centroid decomposition splits a **vertex-set** into $O(\log n)$ levels (so a per-level statistic can work). Path queries → HLD. Pair/global queries with a distance constraint → centroid. Both are $\log$-deep, which is why beginners mix them up.
:::

:::problems
- [[CSES 2079]] Finding a Centroid | https://cses.fi/problemset/task/2079 | easy | the single-level version
- [[CF 342E]] Xenia and Tree | https://codeforces.com/problemset/problem/342/E | hard | the dynamic nearest-marked pattern, $O(\log^2 n)$ per operation
- [[CSES 1133]] Tree Distances II | https://cses.fi/problemset/task/1133 | core | centroid is overkill here — know why rerooting wins
:::