Centroid Decomposition
Recursively split a tree by balanced centroids so global path problems can be reduced to logarithmically many local views.
Centroid Decomposition
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Centroid decomposition is the tree technique for problems where the relevant information depends on paths, but a full all-pairs or all-roots approach is too expensive. The decomposition repeatedly cuts the tree by balanced separators, producing a recursion tree of depth \(O(\log n)\).
Problem-Driven Motivation
Imagine a tree with \(n,q \le 2 \cdot 10^5\). Two online operations are supported:
mark one vertex red,
query the distance from a vertex \(v\) to the nearest red vertex.
The naive answer for each query is a BFS or DFS from \(v\), which is \(O(n)\) per query. Even rerooting or one fixed precomputation does not solve the dynamic update aspect cleanly.
What we need is a way to reduce every query and every update to only \(O(\log n)\) relevant tree nodes. That is exactly what the centroid ancestor chain provides.
Recognition Pattern
Centroid decomposition is a strong candidate when:
the graph is a tree,
the property is about whole paths, not only subtrees,
each query only needs path information aggregated through a few special separators,
there are many updates and queries, and a full traversal per operation is too slow.
Typical contest signals are:
nearest active / colored vertex,
count paths satisfying a distance condition,
optimize over all paths through a chosen pivot,
the statement is about a tree, but subtree-only tools like Euler tour or DSU on tree do not quite fit.
Derivation
A centroid of a tree component is a vertex whose removal leaves no remaining component larger than half the size of the current component.
Why is this useful?
If we recurse after removing the centroid, the recursion depth is \(O(\log n)\).
Every original tree path belongs to exactly one of two categories at each recursive step:
it passes through the current centroid,
or it lies completely inside one recursive child component.
So if we can process all paths that pass through the current centroid, recursion handles the rest.
For dynamic nearest-red queries, the derivation goes further:
every node stores the list of centroid ancestors above it,
for each centroid \(c\), maintain the minimum distance from \(c\) to any red node,
to query a node \(v\), walk through the centroid ancestors of \(v\) and combine \[ dist(v,c) + best[c]. \]
This is the entire trick. The balanced recursion makes the ancestor chain logarithmic.
Worked Problem
Problem.
Initially only node \(0\) is red. Support:
paint(v): make \(v\) red,nearest(v): return distance from \(v\) to the nearest red node.
Why naive fails.
With \(2 \cdot 10^5\) operations, \(O(n)\) BFS per query is impossible.
Step 1: build the centroid tree.
Every node gets a chain of centroid ancestors: \[ v \rightarrow c_0 \rightarrow c_1 \rightarrow \cdots \] where \(c_0\) is the deepest centroid component containing \(v\), \(c_1\) is its parent in the centroid tree, and so on.
Step 2: precompute distances to those ancestors.
For every original node \(v\), store pairs \((c, dist(v,c))\) along that chain.
Step 3: process updates.
When painting \(v\) red, update every centroid ancestor \(c\) of \(v\): \[ best[c] = \min(best[c], dist(v,c)). \]
Step 4: answer queries.
For query node \(u\), try every centroid ancestor \(c\) of \(u\): \[ answer = \min_c \bigl(best[c] + dist(u,c)\bigr). \]
Why this works.
Take the nearest red node \(r\) to \(u\). On the centroid decomposition recursion, there is a highest level where the path \(u \leftrightarrow r\) is split by the current centroid \(c\). That path passes through \(c\), so \[ dist(u,r) = dist(u,c) + dist(r,c). \] The update on \(r\) ensures that \(best[c] \le dist(r,c)\), so the query can recover the right answer from that centroid level.
Implementation Reasoning
The decomposition code has three distinct responsibilities:
compute subtree sizes inside the current component,
find the centroid of that component,
collect distances from every node in the component to this centroid and store them in the node's ancestor list.
The example implementation stores, for each original node, a vector of pairs: \[ (\texttt{centroid}, \texttt{distance to centroid}). \] That is enough to support \(O(\log n)\) updates and queries for the nearest-red problem.
The important implementation invariant is:
For every node \(v\), its stored centroid path contains exactly the centroids of all decomposition components that contain \(v\).
Correctness Intuition
Balanced separators are what make the method fast. The path-splitting argument is what makes it correct. Every query finds the right separator level where the queried path is ``seen'' by one centroid, and every update has already pushed its contribution into that centroid.
Complexity Analysis
building the centroid decomposition: \(O(n \log n)\),
one
paint: \(O(\log n)\),one
nearest: \(O(\log n)\),memory: \(O(n \log n)\) for storing centroid ancestor paths.
Common Pitfalls
Confusing the original tree parent with the centroid-tree parent.
Forgetting that the per-centroid processing still decides whether the final solution is fast enough.
Computing distances to centroid ancestors lazily and accidentally turning queries back into \(O(n)\).
Using centroid decomposition for a plain subtree problem that Euler tour or rerooting solves more directly.
Variants and Failure Modes
Counting or optimizing over paths with a length threshold is a common offline centroid use.
Weighted trees work too, but stored distances become weighted distances.
If queries are about one root and one subtree only, heavy-light or Euler-tour reductions are usually cleaner.
If the update/query structure is global but not path-based, centroid decomposition may be the wrong abstraction.
Practice Problems
Nearest marked node on a tree.
Count paths whose length satisfies a bound.
Path-aggregation problems where a balanced separator naturally splits the path family.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct NearestRedCentroid {
static constexpr int INF = (int)1e9;
int n;
vector<vector<int>> tree;
vector<int> sub_size;
vector<int> removed;
vector<int> centroid_parent;
vector<int> best;
vector<vector<pair<int, int>>> path_to_centroids;
explicit NearestRedCentroid(int n)
: n(n),
tree(n),
sub_size(n, 0),
removed(n, 0),
centroid_parent(n, -1),
best(n, INF),
path_to_centroids(n) {}
void add_edge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
void build() {
decompose(0, -1);
}
void paint_red(int v) {
for (const auto& entry : path_to_centroids[v]) {
int centroid = entry.first;
int dist = entry.second;
best[centroid] = min(best[centroid], dist);
}
}
int query_nearest_red(int v) const {
int answer = INF;
for (const auto& entry : path_to_centroids[v]) {
int centroid = entry.first;
int dist = entry.second;
answer = min(answer, best[centroid] + dist);
}
return answer;
}
private:
void dfs_size(int v, int p) {
sub_size[v] = 1;
for (int to : tree[v]) {
if (to == p || removed[to]) continue;
dfs_size(to, v);
sub_size[v] += sub_size[to];
}
}
int find_centroid(int v, int p, int total) {
for (int to : tree[v]) {
if (to == p || removed[to]) continue;
if (sub_size[to] > total / 2) {
return find_centroid(to, v, total);
}
}
return v;
}
void collect_distances(int v, int p, int dist, int centroid) {
path_to_centroids[v].push_back({centroid, dist});
for (int to : tree[v]) {
if (to == p || removed[to]) continue;
collect_distances(to, v, dist + 1, centroid);
}
}
void decompose(int entry, int parent) {
dfs_size(entry, -1);
int centroid = find_centroid(entry, -1, sub_size[entry]);
centroid_parent[centroid] = parent;
collect_distances(centroid, -1, 0, centroid);
removed[centroid] = 1;
for (int to : tree[centroid]) {
if (!removed[to]) {
decompose(to, centroid);
}
}
}
};
// Example usage:
// build the structure, paint node 0 red, then answer online nearest-red queries.
vector<int> process_nearest_red_queries(
int n,
const vector<pair<int, int>>& edges,
const vector<pair<int, int>>& operations
) {
NearestRedCentroid solver(n);
for (const auto& edge : edges) solver.add_edge(edge.first, edge.second);
solver.build();
solver.paint_red(0);
vector<int> answers;
for (const auto& op : operations) {
int type = op.first;
int v = op.second;
if (type == 1) {
solver.paint_red(v);
} else {
answers.push_back(solver.query_nearest_red(v));
}
}
return answers;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.