Centroid decomposition
Also known as: Centroid decomposition · centroid of a tree · centroid tree · divide and conquer on a tree · nearest marked vertex
How to answer questions about distances in a tree that does not change, while the marks on it do. Take a centroid, a vertex whose removal leaves no part larger than half, and repeat in the parts. There are at most log₂ n levels, and any path passes through a centroid of some level.
The Glottolog catalogue has 7567 languages arranged into families by kinship, and 1937 of them have a long grammar, more than three hundred pages. When a language is poorly described, one of a field linguist's first supports is the nearest described relative: its grammar suggests what to expect. Below is the tree of one language family from Glottolog: the languages on a circle, the subgroups inside. Tap a language without a grammar, and the scene shows its nearest described relative. And if you turn on marking, a tap “publishes” a new grammar, and you can see whom it helped.
Lower Chulym has only a sketch grammar, and the nearest Turkic language with a long one is Old Turkic, four steps away along the tree. Switch to the Trans–New Guinea family: of its 307 languages 27 have a long grammar, and for Uya the nearest described relative is seven steps away. Mark its neighbour Ogea, which so far has only a sketch, and 26 languages at once get closer to a described one.
For one question a breadth-first search from the language to the first marked one would do. For all languages at once, one search from all marked ones. The difficulty is that marks appear one at a time, and questions come mixed in with them. A search per question costs O(n). Centroid decomposition answers in O(log n) and takes a new mark just as quickly.
The idea
A centroid of a tree is a vertex whose removal leaves no part larger than half the tree. Take a centroid, remember the distances from it to all vertices, remove it and do the same in each part. Call the centroid of a part a centroid of the next level. The result is the centroid tree: every vertex sooner or later becomes a centroid itself, and above it stand the centroids of all the pieces it lay in.
Each vertex remembers its distances to its centroids, at most log₂ n + 1 of them. Each centroid remembers the nearest marked vertex in its piece. To mark a vertex, update its centroids; to ask, take the smallest “distance to the centroid plus its nearest marked”.
Here is how the Turkic family splits. First the centroid of the whole family, then a centroid in each remaining piece, and so on down to single vertices. At the end, a question about Lower Chulym: only its centroids are visited.
Why it works
Every tree of n vertices has a vertex whose removal leaves every part with at most n/2 vertices.
Hang the tree from any vertex and compute the subtree sizes. Start at the root. While the current vertex c has a child with a subtree larger than n/2, move into it. The subtree sizes strictly decrease along the way, so the descent ends. At the vertex where it stopped, all children's subtrees are at most n/2. There remains the part “above” c: it has n − size(c) vertices. At the root it does not exist, and we came to any other vertex because size(c) > n/2, so there are fewer than n/2 above it.
The centroid tree has at most ⌊log₂ n⌋ + 1 levels, and each vertex keeps at most ⌊log₂ n⌋ + 1 distances.
A piece of level k is a part left after removing the centroid of a piece of level k − 1, so it has at most half the vertices of that piece, and by induction at most n/2k. A non-empty piece has at least one vertex, so 2k ≤ n and k ≤ log₂ n. A vertex lies in exactly one piece of each level until it becomes a centroid itself, and keeps one distance per level.
For any vertex v the distance to the nearest marked vertex equals the smallest of the numbers dist(v, c) + best(c) over all centroids c above v, where best(c) is the distance from c to the nearest marked vertex of its piece.
Each such number is the length of some route from v through c to a marked vertex, so it is no less than the true distance. Conversely, let m be the marked vertex nearest to v. As long as no vertex of the path from v to m has been taken as a centroid, the whole path lies in one piece: the removed vertices did not touch it. Take the first centroid c that turned out to be on this path. Before that, both v and m lay in the piece of c, so c is one of the centroids above v, and best(c) ≤ dist(c, m). Since c lies on the path, dist(v, c) + dist(c, m) = dist(v, m), and the smallest of the numbers is no greater than the true distance.
Marking a vertex u updates best at its centroids, at most log₂ n + 1 numbers, and a question goes through as many. Preparation is O(n log n): on each level the traversals of the pieces together pass through each vertex at most once.
Code
The pieces are processed level by level without recursion. For each piece: a traversal, subtree sizes, a descent to the centroid as in the proof, and a breadth-first search from the centroid, which writes to each vertex of the piece the pair “centroid, distance”. The marks are the languages with a long grammar; all answers are checked against a breadth-first search from all marked vertices at once.
The tree has 12,208 vertices, families, subgroups, languages, and 11 levels of centroids: as many as the largest family, Atlantic-Congo, which has more than two thousand vertices. On average a vertex keeps 5 pairs. For 1323 languages without a long grammar the nearest neighbour in the subgroup is described, two steps away, while 445 have no described relatives in their family at all: 138 of them are isolates, languages with no known relatives.
What it costs
| Method | Preparation | Mark | Question |
|---|---|---|---|
| Breadth-first search from the question to the first mark | — | O(1) | up to O(n) |
| Search from all marked after every mark | — | O(n) | O(1) |
| Centroid decomposition | O(n log n) | O(log n) | O(log n) |
A measurement on random trees: every tenth of 600 actions is a new mark, the rest are questions, and the first mark is placed at once. Only the actions are measured; the centroids' preparation, O(n log n), is separate.
At 32,000 vertices the search from the question is more than a hundred times slower than centroids in Python and more than two hundred times in Go: there are few marks, and the search has to look through most of the tree before it finds even one. Centroids barely notice the tree growing: a vertex keeps a logarithm of pairs.
Easy mistakes
- Sizes from the old piece. Subtree sizes are recomputed in each piece anew: after a centroid is removed the pieces are smaller, and the old sizes do not apply to them.
- A centroid is not the middle of the diameter. The centre of a tree, the middle of its longest path, splits the tree by length, not by number of vertices. For a broom, a long handle with a bunch of leaves at the end, the centre falls in the middle of the handle, and after removing it the bunch and half the handle stay in one part: more than half the tree.
- The centroid tree is not a subgraph. A centroid's parent in it may be far from it in the original tree; distances must be taken from the recorded pairs, not computed along the edges of the centroid tree.
- Removing marks. The number best(c) can only decrease. If marks are removed, each centroid needs a heap or an ordered set of distances, and operations cost O(log² n).
- A forest. If the tree is a forest, like the tree of languages, the decomposition is built in each family separately, and a question about a language without described relatives honestly returns “none”.
Where it is used
Besides the nearest mark, centroids are the main tool of divide and conquer on trees: to count paths with a given length or weight, each path is counted at the centroid it passes through, and at each centroid the problem reduces to two halves of a path. This is how, for example, the problem Race from the International Olympiad in Informatics 2011 is solved: a path with a weight sum of exactly K and the fewest edges. For questions about the path between two vertices with changes on it, heavy paths are more convenient; for questions about distances with marks, centroids. In linguistics and biology classification trees are huge, and the question “nearest described relative” is asked all the time: for languages by Glottolog, for species by taxonomy.
History
Camille Jordan introduced the centroid of a tree in 1869 in a paper on “assemblages of lines”, proving that every tree has one or two centroids and one or two centres. In competitive programming centroid decomposition became the standard technique of divide and conquer on trees, especially after problems like Race. The Glottolog catalogue on which the scene is built is compiled by Harald Hammarström, Robert Forkel, Martin Haspelmath and Sebastian Bank; it holds languages, their classification and the most complete known description of each language.
Problems
In the problem, marks and questions come mixed together, as in the scene, only without the centroid tree as a hint. Among the tests are the same tree of languages with grammar marks in random order, and a long chain on which the search to the first mark does not make it in time.
A described relativeData: Languages of the world: Glottolog 5.3 (Hammarström, Forkel, Haspelmath & Bank 2026), CC BY 4.0