Rerooting Technique
You know tree DP for one root. Learn to compute answers for all roots in linear time.
Lessons
1. Intro
(Why rerooting matters)
2. The Single-Root Problem (Why you need rerooting)
(The $O(n^2)$ problem)
3. Rerooting Intuition (Reusing previous work)
(Incremental updates)
4. The Two-Pass Algorithm (Down and up)
(The core algorithm)
5. Down Pass (Computing subtree answers)
(Subtree DP)
6. Up Pass (Propagating parent contributions)
(Parent contributions)
7. Combining Down and Up (Final answers)
(Merging results)
8. Contribution (What each subtree gives)
(Child contribution logic)
9. Prefix-Suffix Arrays (Excluding one child)
(Efficient sibling exclusion)
10. Rerooting Template (General pattern)
(Apply to any problem)
11. Problem - Tree Distances II (CSES 1133)
(CSES problem)
12. Core Observation (Moving root changes distances)
(Distance shift insight)
13. Down Pass (Subtree distances)
(Subtree sums)
14. Up Pass (Parent contribution)
(Outside contributions)
15. Final Answer (Combining down and up)
(Merge down and up)
16. Tree Distances II - Implementation (Two DFS passes)
(C++ code)
17. Walkthrough (Small tree example)
(4-node tree)
18. Lessons Learned (Sum aggregation)
(Distance aggregation)
19. Problem - Sum of Distances in Tree (LeetCode 834)
(LeetCode variant)
20. Implementation Notes (Array indexing)
(0-indexed implementation)
21. Complexity Analysis (Linear time)
O(n) proof
22. Rerooting vs Brute Force (Why rerooting wins)
($n$ times faster)
23. When to Use Rerooting (Problem patterns)
(All-roots signal)
24. State Design (What to track)
(DP state choice)
25. Handling Multiple Children (Prefix-suffix pattern)
(Sibling combination)
26. Rerooting with Max (Not just sum)
(Maximum problems)
27. Rerooting with Count (Combinatorial problems)
(Distance histograms)
28. Edge Cases (Small trees)
(n=1 and n=2)
29. Debugging Rerooting (Common mistakes)
(Double-counting)
30. Rerooting Variations (Different problems)
(3-pass extensions)
31. Practice Tips (Getting comfortable)
(Solve 5 problems)
32. Quiz: Rerooting Answer
Knowledge check
33. Quiz: Rerooting Up Value
Knowledge check
34. Quiz: Rerooting Selection
Knowledge check
35. Common Mistakes (What to avoid)
(Exclude child correctly)
36. Rerooting in Contests (Recognition)
(For each node signal)
37. Advanced Rerooting (Multiple states)
(Tuple states)
38. Rerooting with Updates (Dynamic trees)
(Rare dynamic case)
39. Section Recap
(Two-pass proficiency)