You have a tree with 100,000 nodes, and someone asks you to answer thousands of distance queries between arbitrary pairs of nodes. Or maybe you need to find the closest "marked" node to a given node, and marks keep getting added over time. A naive DFS for each query gives you O(n) per query, which is far too slow when both the tree and the number of queries are large.

Centroid decomposition is the technique that turns these O(n)-per-query problems into O(log n) per query. It works by recursively finding the "center" of the tree, using it to process all paths that pass through that center, and then decomposing the remaining subtrees the same way. The result is a new tree, the centroid tree, with only O(log n) depth, and this shallow structure is what makes fast queries possible.

Tree path queries come up constantly in competitive programming and occasionally in interviews at companies that test advanced algorithmic thinking. The challenge is that trees do not have the nice linear structure of arrays, where you can apply prefix sums or segment trees directly. Paths in trees can twist and turn, and two nodes that are far apart in the tree might have a path that passes through many intermediate nodes.

Centroid decomposition gives you a systematic way to handle any problem that involves processing all paths in a tree, or answering queries about paths efficiently. Here is where it shows up:

The Problem

Suppose you have an unrooted tree with n nodes and you want to count how many paths have a total weight equal to some target k. The brute force approach is to run a DFS from every node, exploring all possible paths. That is O(n^2) in the worst case, since each DFS can visit up to n nodes and you start from each of the n nodes.

For a single query like "what is the distance from u to v?", you can answer it in O(n) with a single BFS or DFS. But if you have q queries, that becomes O(n * q), which is too slow when both n and q are around 100,000.

We need a way to preprocess the tree so that each query takes much less than O(n).

The Key Insight

Here is the central observation: every tree has a centroid, a node whose removal splits the tree into components where no component has more than n/2 nodes. This is a powerful guarantee. It means that if you pick the centroid and remove it, every remaining subtree is at most half the size of the original tree.

Why does this matter? Because you can use a divide-and-conquer strategy:

Since each subtree is at most half the size, the recursion depth is O(log n). And at each level of recursion, the total work across all subtrees is O(n) (because the subtrees partition the nodes). This gives O(n log n) total work for the entire decomposition.

The result of this recursive process is a new tree called the centroid tree. In the centroid tree, the centroid of the original tree is the root, and its children are the centroids of the subtrees that remained after removing it. This centroid tree has depth O(log n), and it has a remarkable property: for any two nodes u and v in the original tree, their path passes through their lowest common ancestor (LCA) in the centroid tree.

The Analogy

Think of it like setting up distribution hubs for a country. If you want to efficiently route packages between any two cities, you find the geographic center of the country and build a hub there. Every package route can go through this central hub. Then for each region that remains, you find its center and build a regional hub. You keep going until every small area has its own local hub. The hierarchy of hubs (national, regional, local) has only a few levels because each level halves the area. Any package route only needs to go up and down through O(log n) hubs.

Visual Overview

The following diagram shows the high-level idea. You start with a tree, find its centroid, remove it, and recurse on the pieces. The centroids form a new tree with logarithmic depth.

Step 1: Finding the Centroid

To find the centroid of a tree (or subtree) with n nodes, you need to:

Here is the key formula. For a node v with children c1, c2, ..., ck in the rooted tree:

Every tree has at least one centroid (and at most two, in which case they are adjacent). We only need one, so we pick the first one we find.

Step 2: Process Paths Through the Centroid

Once you have the centroid, you know that every path in the current tree either:

Paths in the second category will be handled by the recursive calls. So at this level, you only need to process paths that pass through the centroid. This is the "conquer" step and it depends on the specific problem you are solving. For distance queries, you might store the distance from the centroid to every node in the current tree. For counting paths of weight k, you might use a hash map to count complementary distances.

Step 3: Remove the Centroid and Recurse

After processing, you mark the centroid as "removed" (so future DFS calls skip it) and recurse on each remaining connected component. Each component is a subtree rooted at one of the centroid's neighbors (in the current tree), and each has size at most n/2.

The centroid found in each recursive call becomes a child of the current centroid in the centroid tree. This builds the centroid tree implicitly as the recursion proceeds.

The Complete Decomposition Process

Let us work through a concrete example with a tree of 7 nodes. The tree looks like this:

Edges: (1,2), (1,3), (2,4), (2,5), (3,6), (5,7). All edges have weight 1 for simplicity.

Round 1: Finding the Centroid of the Full Tree

The tree has 7 nodes. We need a node whose removal leaves no component larger than 7/2 = 3.

First, root the tree at node 1 and compute subtree sizes:

Now check each node. When we remove a node from a tree of size 7, the components are its child subtrees plus the "upward" component.

Node 2 has a max component size of 3, which is at most 7/2 = 3.5. So node 2 is the centroid.

Round 1: Removing Node 2

After removing node 2, three components remain:

Round 2: Recurse on Each Component

Component A: {4} has a single node. Node 4 is trivially its own centroid. It becomes a child of node 2 in the centroid tree.

Component B: {5, 7} has 2 nodes. Node 5 is the centroid (removing it leaves {7}, which has size 1 <= 2/2 = 1). Node 5 becomes a child of node 2. After removing node 5, we recurse on {7}. Node 7 becomes a child of node 5.

Component C: {1, 3, 6} has 3 nodes. Let us check:

Node 3 is the centroid. It becomes a child of node 2. After removing node 3, components are {1} and {6}. Each is a single node and becomes a child of node 3.

Final Centroid Tree

Notice the depth is only 3 (for 7 nodes). The original tree had depth 4 (path 1-2-5-7). The centroid tree is shallower because every split is balanced.

Key property to verify: Consider the path from node 7 to node 6 in the original tree. That path is 7-5-2-1-3-6. In the centroid tree, the LCA of nodes 7 and 6 is node 2 (since 7 is under 5, which is under 2, and 6 is under 3, which is under 2). The original path does indeed pass through node 2. This is not a coincidence. Every path in the original tree passes through the LCA of its endpoints in the centroid tree.

Here is a complete implementation of centroid decomposition with a distance query application. The code builds the centroid tree, precomputes distances from each node to all its ancestors in the centroid tree, and then answers distance queries by checking the LCA in the centroid tree.

Let us walk through the key parts of the implementation.

computeSize (DFS for Subtree Sizes)

This function roots the current (non-removed) subtree at an arbitrary node and computes how many nodes each subtree contains. It skips any node already marked as removed, because those nodes were centroids at a previous level and are no longer part of the current subproblem. This is a standard DFS that runs in O(size of current component).

findCentroid (Greedy Descent)

Rather than checking every node, this function uses a greedy approach. Starting at any node, it looks at each child's subtree size. If a child's subtree has more than treeSize/2 nodes, the centroid must be in that subtree (because removing the current node would leave a component too large). So it descends into that child and repeats. When no child has a subtree exceeding treeSize/2, the current node is the centroid.

This works because the "upward" component for any node in the descent path keeps getting smaller as we go deeper, while the large child subtree keeps shrinking as we enter it. The process converges to the centroid in O(n) time.

computeDistances (Precomputing Ancestor Distances)

For the distance query application, we need to know the distance from every node to each of its ancestors in the centroid tree. When we find centroid c at depth d, we run a DFS from c to all non-removed nodes and store distToAncestor[node][d] = distance from node to c. This way, when we later query distance(u, v), we can check every common ancestor depth and compute distToAncestor[u][d] + distToAncestor[v][d].

query (Distance Lookup)

The distance between u and v in the original tree equals distToAncestor[u][d] + distToAncestor[v][d] where d is the depth of their LCA in the centroid tree. Since we do not explicitly compute the LCA, we check all depths from 0 to min(depth[u], depth[v]) and take the minimum. The correct LCA depth will give the true distance, and all other depths give upper bounds (because the triangle inequality holds), so the minimum is the correct answer.

Common Mistakes

Build Time: O(n log n)

The build time is O(n log n), and here is why.

The recursion has O(log n) levels. At each level, the centroid splits the current tree into subtrees of size at most n/2, so the depth doubles at most log2(n) times before reaching size 1.

At each level of the recursion, the total work across all subproblems is O(n). This is because the subtrees at any given recursion level form a partition of the n nodes (each node belongs to exactly one subtree at each level). Computing sizes, finding the centroid, and computing distances for a subtree of size s all take O(s) time, and the sizes sum to n.

Therefore: O(log n) levels times O(n) work per level = O(n log n) total.

This is the same reasoning that gives merge sort its O(n log n) complexity. Each level processes all n elements, and there are O(log n) levels.

Query Time: O(log n)

Each query checks all depths from 0 to the depth of the shallower node. Since the centroid tree has depth O(log n), each query takes O(log n) time.

Space: O(n log n)

The dominant space cost is the distToAncestor table: n nodes, each storing distances to O(log n) ancestors. The adjacency list, size arrays, and boolean flags all use O(n) space.

Variation 1: Closest Marked Node (Dynamic Updates)

This is one of the most practical applications. You maintain a set of "marked" nodes that changes over time, and you need to answer queries of the form "what is the closest marked node to u?"

For each node in the centroid tree, maintain a value best[c] representing the minimum distance from c to any marked node in c's subtree (in the centroid tree). When you mark node u, walk up from u to the root of the centroid tree, updating best[ancestor] = min(best[ancestor], dist(u, ancestor)). When you query node u, walk up the same path and compute min over all ancestors a of (best[a] + dist(u, a)).

Both update and query walk O(log n) ancestors, so they take O(log n) time each.

Variation 2: Counting Paths of Weight K

Given a tree with weighted edges, count the number of paths with total weight exactly k. At each centroid c, compute the distance from c to every node in its subtree. Store these distances in a frequency map. For each distance d, the number of paths through c with weight k is the number of nodes at distance d times the number of nodes at distance k - d (being careful not to double count paths within the same child subtree).

This gives an O(n log n) algorithm for the entire counting problem. The classic version of this problem is known as "Race" or "IOI 2011 Race."

Variation 3: Centroid Decomposition with Edge Updates

If edge weights change, you cannot use the precomputed distance table directly. However, the structure of the centroid tree does not change (it depends only on the tree's topology, not the weights). You can rebuild the distance tables in O(n log n) after weight changes, or use lazy techniques to handle updates more efficiently for specific problem types.

Comparison Table

Centroid decomposition is not the only way to handle tree path queries. Here is how it compares to the alternatives.

When to Choose Centroid Decomposition

When NOT to Use Centroid Decomposition

Pattern 1: Distance Queries

Problem type: Given a tree with weighted edges and q queries, each asking for the distance between two nodes u and v.

How centroid decomposition helps: Build the centroid tree and precompute distances from each node to all its centroid tree ancestors. Each query is answered in O(log n) by checking all common ancestors and taking the minimum of dist(u, ancestor) + dist(v, ancestor). Total time: O(n log n + q log n).

Pattern 2: Counting Paths with a Given Property

Problem type: Count the number of paths in a tree whose total weight equals k, or whose length (number of edges) is at most k.

How centroid decomposition helps: At each centroid, gather all distances from the centroid to nodes in its subtree. Use a hash map or sorted array to count pairs that satisfy the property. Subtract pairs that are in the same child subtree (to avoid double counting). Recurse on each subtree.

Pattern 3: Closest Marked Node

Problem type: Maintain a set of marked nodes that changes over time. Answer queries of the form "what is the distance to the closest marked node from u?"

How centroid decomposition helps: For each centroid tree ancestor of u, maintain the minimum distance to any marked node in that ancestor's subtree. Updates and queries each walk O(log n) ancestors.

Interview Tips

Key Takeaways

Quick Reference