Section Recap

You learned what a centroid is and how to find one in $O(n)$ time by walking toward heavy subtrees. You built the centroid decomposition tree by recursively removing centroids, creating a structure with $O(\log n)$ depth. You solved path-counting problems by processing paths through centroids and recursing on components.

You handled exact-length paths and range-length paths with the same pattern, only changing the counting step. You now recognize when to use centroid decomposition: whole-tree path problems where DFS and DP fall short. Next section: advanced topics and competition strategies.