Centroid Decomposition
Some distance problems resist DFS and DP. Centroid decomposition gives divide-and-conquer on trees.
Lessons
1. Intro
(Divide and conquer on trees)
2. Why Centroid Decomposition?
(When DFS and DP fail)
3. What is a Centroid?
(The balance point of a tree)
4. Centroid Existence Proof
(Every tree has one)
5. Finding the Centroid
(Walk toward heavy subtrees)
6. Example: Finding a Centroid
(Walking through the process)
7. Centroid Properties
Why it works for divide-and...
8. Quiz: Centroid Properties
Knowledge check
9. The Centroid Decomposition Tree
Recursive structure of cent...
10. Why Depth is O(log n)
(Each level halves the size)
11. Quiz: Decomposition Tree Depth
Knowledge check
12. Building the Decomposition Tree
(Recursive centroid finding)
13. Decomposition Tree vs Original Tree
(Two different structures)
14. Paths Through Centroids
core idea for path problems
15. Divide and Conquer on Trees
(The general pattern)
16. Problem - Finding a Centroid
(CSES 2079)
17. Read Statement
(Problem link)
18. Core idea 1 - Subtree Sizes
(Compute sizes with DFS)
19. Core idea 2 - Walk to Heavy Subtree
(Move toward balance)
20. Algorithm - Find Centroid
(Two-phase approach)
21. Finding a Centroid - Implementation
(Complete solution)
22. Walkthrough
(Tracing the algorithm)
23. Lessons Learned
(summary)
24. Quiz: Finding the Centroid
Knowledge check
25. Problem - Fixed-Length Paths I
(CSES 2080)
26. Read Statement
(Problem link)
27. Core idea 1 - Paths Through Centroid
(Divide by centroid)
28. Core idea 2 - Combining Subtree Paths
Count distances from centroid
29. Core idea 3 - Subtract Same-Subtree Paths
Avoid counting paths within...
30. Algorithm - Count Paths Through Centroid
(The recursive structure)
31. Fixed-Length Paths I - Implementation
(Complete solution)
32. Walkthrough
(Example trace)
33. Lessons Learned
(Path counting with centroids)
34. Quiz: Counting Paths Through Centroid
Knowledge check
35. Problem - Fixed-Length Paths II
(CSES 2081)
36. Read Statement
(Problem link)
37. Core idea - Count Range Instead of Exact
(Modify the counting step)
38. Algorithm - Count Paths in Range
(Range query on distances)
39. Fixed-Length Paths II - Implementation
(Range counting with map)
40. Walkthrough
(Example with range)
41. Lessons Learned
(Range queries on paths)
42. Distance Queries with Centroid Decomposition
Preprocessing for fast queries
43. When to Use Centroid Decomposition
(Problem recognition)
44. Quiz: When to Apply Centroid Decomposition
Knowledge check
45. Centroid Decomposition vs Other Techniques
(Choosing the right tool)
46. Implementation Tips
(Avoiding common mistakes)
47. Complexity Analysis
(Why it's O(n log n))
48. Space Complexity
(Memory usage)
49. Variations and Extensions
(Beyond basic path counting)
50. Debugging Centroid Decomposition
(Common errors and fixes)
51. Practice Problems
(Build your skills)
52. Check Your Understanding
(Centroid definition)
53. Check Your Understanding
(Decomposition depth)
54. Check Your Understanding
(Path counting logic)
55. Section Recap
(What you learned)