When to Use Centroid Decomposition

Use centroid decomposition when you need to process all paths in a tree efficiently. The $O(\log n)$ depth ensures each node participates in only $O(\log n)$ centroid computations.

How do you recognize centroid problems? Look for keywords: count paths, path queries, or tree distances with constraints. If simpler techniques like tree DP fail due to complexity, centroid decomposition often works.