Centroid Decomposition
You know tree DP. Now divide trees by centroids. Solve path-counting problems where brute force fails and centroid decomposition runs in O(n log n).
Lessons
1. Introduction to Centroid Decomposition
Divide and conquer on trees
2. What Centroid Decomposition Solves
Path counting, nearest queries
3. When to Use Centroid Decomposition
All paths pass through some centroid
4. Centroid Decomposition Template
The decomposition template
5. When Centroid Decomposition Helps
Problem type patterns
6. Problem - IOI Race
IOI 2011 - min edges for weight K
7. IOI Race - Why Naive Fails
Optimize over paths through centroid
8. IOI Race - Defining the DP
best[w] = min edges for weight w
9. IOI Race - Implementation
Clear best after each centroid
10. IOI Race - Time and Space
O(n log n) with proper cleanup
11. Problem - Distance in Tree
CF 161D - pairs at distance k
12. Distance in Tree - Why Naive Fails
Each pair passes through one centroid
13. Distance in Tree - Defining the DP
Count pairs, not paths
14. Distance in Tree - Core Logic
Merge subtree counts carefully
15. Distance in Tree - Implementation
cnt[d] tracks seen distances
16. Problem - Xenia and Tree
CF 342E - nearest red node queries
17. Xenia and Tree - Why Naive Fails
Centroid ancestors store min distances
18. Xenia and Tree - Defining the DP
O(log n) ancestors per node
19. Xenia and Tree - Core Logic
Update all ancestors on paint
20. Xenia and Tree - Implementation
Query all ancestors, take min
21. Problem - Close Vertices
CF 293E - distance ≤ l, weight ≤ w
22. Close Vertices - Solution
Sort by distance, two-pointer + BIT
23. Quiz: Centroid Properties
What makes a centroid?
24. Quiz: Counting Paths
Subtree merging patterns
25. Common Mistakes in Centroid Decomposition
Forgot to remove, no reset
26. Problem - Digit Tree
CF 715C - digit paths
27. Digit Tree - Solution
The solution
28. Problem - Query on a Tree V
SPOJ QTREE5 - colored queries
29. Query on a Tree V - Solution
The solution
30. Section Recap
Split at centroid, process recursively