Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 63 ยท Graphs for Contests

Centroid Decomposition for Contests

Use centroid decomposition to count tree paths of length exactly k or at most k in O(n log n), with an iterative Python implementation verified by brute force.

Many tree problems ask about pairs of vertices: how many pairs are exactly k edges apart, how many are at most k apart, what is the sum of all pairwise distances? Checking every pair costs O(n^2), too slow for n = 10^5. Binary lifting answers a single distance quickly, but it does not help you count over all pairs.

Centroid decomposition is the divide-and-conquer that fits trees. The data-structures version of this idea shows how to build the centroid tree and how to answer nearest-marked-vertex queries. This lesson is the contest recipe for the other classic use: counting paths, written iteratively so it survives a path of 10^5 vertices in Python.

The recipe in one picture

A centroid of a tree with n vertices is a vertex whose removal leaves components of at most n / 2 vertices each. Every tree has one. The decomposition works like this:

  1. Find the centroid c of the current component.
  2. Count every path that passes through c.
  3. Delete c, and repeat the whole procedure on each remaining component.

Every path in the tree is counted exactly once: at the first centroid that lies on it. Because each component is at most half as big as its parent, the recursion has only about log2(n) levels, and each level touches every vertex a constant number of times. The total is O(n log n) if step 2 is linear (or O(n log^2 n) if it needs a sort).

flowchart TD
    T["Whole tree, n vertices"] -->|"pick centroid c1, count paths through c1"| A["Component A, at most n/2"]
    T --> B["Component B, at most n/2"]
    A -->|"centroid c2"| A1["at most n/4"]
    A --> A2["at most n/4"]
    B -->|"centroid c3"| B1["at most n/4"]

Components shrink geometrically, so a vertex belongs to at most about log2(n) + 1 of them.

Counting paths of length exactly k

Fix a centroid c. Every vertex v in its component has a distance d(v) from c. A path through c that joins u and v has length d(u) + d(v), provided u and v lie in different branches (different neighbors of c). If they were in the same branch, the real path would not touch c and would be shorter, so those pairs must not be counted here; they are counted deeper in the recursion.

So process the branches one by one. Keep seen[d] = number of vertices already processed (in earlier branches, plus c itself at distance 0) at distance d. For every vertex v of the new branch, add seen[k - d(v)] to the answer. Then, only after the whole branch is checked, add its vertices to seen. Adding them afterwards is what keeps a branch from pairing with itself.

The code below has three parts: find the centroids iteratively (compute sizes, then walk towards a child that is too heavy), collect distances per branch, and count. A random-tree test compares it against a BFS from every vertex.

Python Count pairs at distance exactly k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The path of 6 vertices has 5, 4, 3, 2, 1 pairs at distances 1 to 5, as it should. The seen array has size k + 1, so one centroid costs O(component size + k), and k should be bounded by the component size to keep the total at O(n log n): cap k with min(k, size), or discard distances above k, as the code does with if d <= k.

Counting paths of length at most k

For "at most k" you cannot use a frequency array indexed by exact distance directly, but sorting works. At a centroid, take the list of all distances (including 0 for c) and count pairs with d(u) + d(v) <= k using sort plus two pointers. That count includes the invalid pairs that live in the same branch, so subtract, for each branch, the same count computed on that branch alone. Both lists measure distance from c, so the invalid pairs are over-counted by exactly the same amount and cancel.

This add the whole, subtract the parts pattern is the standard way to avoid the "different branch" bookkeeping. It costs one sort per level, so O(n log^2 n) overall.

Python Count pairs within distance k, and measure the depth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last loop measures how many components each vertex belongs to on a long path, the worst case for most tree algorithms. The depth equals floor(log2 n) + 1, confirming the logarithmic bound that makes the technique work.

Variations that follow the same template

Question What step 2 computes
Pairs at distance exactly k frequency array by distance (this lesson)
Pairs at distance at most k sorted distances, two pointers, subtract same-branch pairs
Sum of all pairwise distances per centroid: sum of d(u) + d(v) over pairs in different branches
Nearest marked vertex per centroid: minimum distance to a marked vertex; query walks the centroid ancestors
Paths whose edge weights sum to k same, with weighted distances in a dictionary
Longest path with at most m special edges per centroid: best length per number of special edges, merged branch by branch

For paths with weights, replace the BFS by a traversal that adds the edge weights, and use a dictionary instead of an array indexed by distance.

Pitfalls

  • Forgetting to delete the centroid. Mark it as removed before recursing, or the next component search walks back into it.
  • Pairing a branch with itself. Update seen only after the whole branch is processed, or use the add-all-subtract-parts pattern.
  • Recursion depth. Even though the centroid tree is shallow, the DFS inside a component can be 10^5 deep. Use the iterative traversal shown here.
  • Double counting. Count unordered pairs once. The seen approach counts each pair when its second vertex is processed, so no division by two is needed.
  • Choosing the wrong tool. If all you need is the distance between a few pairs, LCA is simpler. If subtrees are the object, an Euler tour is simpler. Centroid decomposition is for questions over all pairs, or queries involving "some vertex of a set".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the centroid decomposition have only O(log n) levels?

    By definition removing a centroid leaves components of size at most n/2, so sizes at least halve at each level.
  2. 2. When counting paths through the centroid c, why must the two endpoints lie in different branches?

    Inside one branch the real path stays in that branch. Adding the two distances to c would overestimate its length.
  3. 3. In the exact-k counting loop, why is seen updated only after the whole branch has been scanned?

    Updating immediately would let a vertex pair with an earlier vertex of the same branch, which is the invalid case.
  4. 4. What is the total running time of the exact-k counting when each centroid costs time linear in its component?

    There are O(log n) levels and every vertex appears in one component per level, so the total linear work per level adds up to O(n log n).

Summary

  • Centroid decomposition removes a centroid, counts all paths through it, and recurses on the remaining components, which have at most half the size.
  • Each path is counted once, at the first centroid on it, and there are O(log n) levels.
  • For exactly k, process branches in order with a frequency array of distances, updating it after each branch.
  • For at most k, sort the distances, count with two pointers, and subtract the same-branch pairs.
  • Implement the component search iteratively and always test against a brute force on small random trees.

Next: Maximum Flow and Matching in Contest Practice