Chapter 11 · Advanced Tree Algorithms
Centroid Decomposition
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.
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 ≤ log2 n.
Every root-to-leaf path in the centroid tree has length ≤ log2 n + 1, and the total work is O(nlog n) if each level's component sizes are summed over that level (each vertex participates in ≤ log n levels, and finding a centroid within a component costs time linear in its size).
By the centroid property, the component containing any vertex v after removing its centroid has size ≤ half of the current component. So along a centroid-tree root-to-leaf path the component sizes decrease geometrically, giving ≤ log2 n levels, and each vertex is "worked on" once per level it appears in. ∎
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);
}build recurses ≤ log n deep, so it is safe; the inner sz DFS is O(component) deep — on a path of 106 vertices that is a stack overflow. Either make the size DFS iterative, or keep the habit of stating n ≤ 2· 105 and adding ulimit -s unlimited to the harness (Walks, Trails, Paths, Cycles).
#The counting pattern
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).
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.
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(size), total O(n log n)), - count pairs with dist ∈ [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 Small-to-Large Merging,
- nearest marked vertex (dynamic!) → keep at each vertex its ≤ log n centroid ancestors, each with a multiset of distances to marked vertices in its component: point update O(log2 n), query O(log2 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.
- 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
allonly from previous children as above. - Reusing the frequency array across centroids without clearing the touched entries only — a full
fillper level is O(n) per level only if sized by component; on 106 this is fine, but on many test cases it becomes O(T n); use a touched-list. - Distance measured in the original tree vs. in the component: paths through c are shortest paths in T (unique path), so distT(u,v) = dist(u,c) + 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.
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.
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.