#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/centroid-decomposition

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/centroid-decomposition

Lessons

1. Intro

2. Why Centroid Decomposition?

3. What is a Centroid?

Practice Problems

Ready to start learning?

4. Centroid Existence Proof

5. Finding the Centroid

6. Example: Finding a Centroid

7. Centroid Properties

8. The Centroid Decomposition Tree

9. Why Depth is O(log n)

10. Building the Decomposition Tree

11. Decomposition Tree vs Original Tree

12. Paths Through Centroids

13. Divide and Conquer on Trees

14. Problem - Finding a Centroid

15. Read Statement

16. Key idea 1 - Subtree Sizes

17. Key idea 2 - Walk to Heavy Subtree

18. Algorithm - Find Centroid

19. Finding a Centroid - Implementation

20. Walkthrough

21. Lessons Learned

22. Problem - Fixed-Length Paths I

23. Read Statement

24. Key idea 1 - Paths Through Centroid

25. Key idea 2 - Combining Subtree Paths

26. Key idea 3 - Subtract Same-Subtree Paths

27. Algorithm - Count Paths Through Centroid

28. Fixed-Length Paths I - Implementation

29. Walkthrough

30. Lessons Learned

31. Problem - Fixed-Length Paths II

32. Read Statement

33. Key idea - Count Range Instead of Exact

34. Algorithm - Count Paths in Range

35. Fixed-Length Paths II - Implementation

36. Walkthrough

37. Lessons Learned

38. Distance Queries with Centroid Decomposition

39. When to Use Centroid Decomposition

40. Centroid Decomposition vs Other Techniques

41. Implementation Tips

42. Complexity Analysis

43. Space Complexity

44. Variations and Extensions

45. Debugging Centroid Decomposition

46. Practice Problems

47. Check Your Understanding

48. Check Your Understanding

49. Check Your Understanding

50. Section 17 Recap