Centroid Decomposition

A tree is one of the simplest data structures: $n$ nodes connected by $n-1$ edges, no cycles, a unique path between every pair of nodes. Trees turn up everywhere — file systems, family pedigrees, parse trees in compilers, phylogenetic trees in biology.

Now ask a natural question: how many paths in the tree have exactly length $k$? A path here is any sequence of distinct adjacent nodes. The naive answer visits every pair of nodes and measures the distance between them — $O(n^2)$ work, which becomes painfully slow the moment $n$ climbs into the millions.

The clever answer is centroid decomposition, a divide-and-conquer technique that cuts the tree at precisely the right node and lets you count every path in $O(n \log n)$ time. The key insight is deceptively simple: every path either passes through the centroid of the current tree, or it lives entirely in one of the smaller subtrees left after you remove it. Solve the first kind, recurse on the second.

The tree below has 11 nodes. Pick a target length $k$ and press Run to watch centroid decomposition count every path of that length. The centroid at each recursive level is highlighted in orange; paths that cross it are tallied before the algorithm recurses into the remaining subtrees.

<div class="controls">
  <label>{{label_k}} <input id="kInput" type="number" min="1" max="6" value="3"></label>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="layout">
  <canvas id="treeCanvas" width="480" height="260"></canvas>
  <div class="panel">
    <div id="logBox" class="logbox"></div>
    <div class="result" id="result"></div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; }
#kInput { width: 3.5rem; padding: .25rem .4rem; font-size: .9rem; border: 1px solid #aaa; border-radius: 5px; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.layout { display: flex; gap: .8rem; flex-wrap: wrap; }
canvas { border: 1px solid #dde; border-radius: 8px; background: #f8fafc; flex-shrink: 0; max-width: 100%; }
.panel { flex: 1 1 160px; display: flex; flex-direction: column; gap: .5rem; }
.logbox { font-size: .8rem; line-height: 1.55; color: #334; background: #f4f6f8;
          border: 1px solid #dde; border-radius: 7px; padding: .5rem .7rem;
          max-height: 190px; overflow-y: auto; }
.logbox p { margin: 0 0 .2rem; }
.logbox .hi { color: #d97706; font-weight: 600; }
.logbox .found { color: #0a7d33; font-weight: 600; }
.result { font-size: 1rem; font-weight: 700; color: #1d3557; min-height: 1.4em; }

// Code not found

Notice the depth of the recursion: the centroid splits the tree so that no subtree has more than half the nodes, so the recursion is at most $O(\log n)$ levels deep. At each level the algorithm scans every node once, giving $O(n)$ work per level and $O(n \log n)$ total — regardless of the shape of the tree.

The efficiency of centroid decomposition rests on one provable fact about trees:

Centroid existence theorem. Every tree with $n \ge 1$ nodes has at least one centroid — a node whose removal leaves no subtree with more than $\lfloor n/2 \rfloor$ nodes. It can be found in $O(n)$ by a single DFS that computes subtree sizes.

That guarantee means each recursive call receives a tree at most half the size of its parent. The recursion depth is therefore at most $\lceil \log_2 n \rceil$. Because each level touches every node exactly once (across all parallel subproblems), the total work is $O(n \log n)$.

Compare this to the naive $O(n^2)$ brute force: on a tree with $n = 10^6$ nodes, brute force requires $10^{12}$ operations, while centroid decomposition needs roughly $2 \times 10^7$ — a factor of $50{,}000$ improvement.

The technique is not a Millennium Problem and is not open: it is a solved, classical algorithm well established in competitive programming and combinatorics since the 1980s. Its status is proven correct and optimal for this class of problems — the $O(n \log n)$ bound is tight, achieved by a path graph where the centroid always sits in the middle.

Centroid decomposition is closely related to divide and conquer on trees and shares the same philosophy as merge sort: always split at the balance point to bound the recursion depth.

Any problem of the form "aggregate something over all paths in a tree" becomes tractable with centroid decomposition:

• Competitive programming: counting paths of length $k$, finding the number of paths with sum $S$, or answering distance queries between arbitrary node pairs — all classic contest problems solved in $O(n \log n)$ or $O(n \log^2 n)$.
• Road networks: city maps modeled as trees (spanning trees of planar graphs) admit fast point-to-point distance queries after centroid decomposition preprocessing — used in routing and logistics software.
• Genome assembly graphs: sequence overlap graphs in bioinformatics are often tree-like; centroid decomposition speeds up repeat-detection passes over long genomic paths.
• Network monitoring: in tree-topology data-center networks, centroid decomposition underlies efficient broadcast and aggregation schemes that minimize message hops.
• Offline LCA and distance queries: centroid decomposition is one of the standard tools alongside shortest-path techniques for answering batches of tree-path queries faster than handling each one independently.

The core idea — always recurse on balanced halves — reappears in segment trees, merge sort, and binary search. Centroid decomposition is simply that idea applied to the irregular topology of a tree.

Centroid decomposition is a beautiful example of how the right decomposition collapses an exponential wall. Every path in a tree passes through exactly one centroid in the decomposition hierarchy — so you only need to count the crossing paths at each level, then recurse. The balance guarantee keeps the hierarchy shallow, and the total work stays $O(n \log n)$.

The next time you face a problem that asks "how many tree paths satisfy property $X$?", reach for the centroid: find it in $O(n)$, count the crossing paths in $O(n)$ or $O(n \log n)$, remove it, and recurse. The recursion depth is at most $\log_2 n$, and your solution runs in a budget any modern machine can meet — even for trees with millions of nodes.