When to Use Centroid Decomposition

Use centroid decomposition when the problem involves all paths in a tree and simpler methods time out. Classic signals: counting paths with a property, distance queries across many pairs, or combining information across different parts of the tree. If the problem only cares about root-to-leaf paths, DFS or DP is simpler.

If it is about subtree queries, subtree DP works. Centroid decomposition is for whole-tree path problems. The $O(n \log n)$ time makes it viable for $n \le 200,000$, which covers most competitive programming constraints.