Tree Algorithms
You've done DP on general graphs. Now use tree structure. Solve rerooting DP problems where you compute answers for every node as root.
Lessons
1. Introduction to Tree Algorithms
Connected, no cycles, n-1 edges
2. What Tree Problems Solve
Hierarchies, file systems, game trees
3. Problem - Possible Root Nodes
LC 2581 - count valid root nodes
4. Possible Root Nodes - Why Naive Fails
Reroot: one root's answer to another
5. Possible Root Nodes - Defining the DP
correct[v] = guesses when rooted at v
6. Possible Root Nodes - Transition
Edge flip: +1 or -1 to count
7. Possible Root Nodes - Base Cases
Root at 0, count initial correct
8. Possible Root Nodes - Implementation
Two DFS: first root, then reroot
9. Rerooting DP Template
The rerooting template
10. Possible Root Nodes - Time and Space
O(n + g) for g guesses
11. Binary Lifting Template
The binary lifting template
12. Problem - Min Diameter After Merge
LC 3203 - connect two trees optimally
13. Min Diameter After Merge - Why Naive Fails
Merged diameter ≥ max original
14. Min Diameter After Merge - Defining the DP
Connect centers, not random nodes
15. Min Diameter After Merge - Core Logic
Two BFS finds diameter endpoints
16. Min Diameter After Merge - Implementation
max(d1, d2, r1 + r2 + 1)
17. Problem - Min Edge Reversals
LC 2858 - reversals for reachability
18. Min Edge Reversals - Why Naive Fails
Edge toward root costs 1
19. Min Edge Reversals - Defining the DP
0 for forward, 1 for backward
20. Min Edge Reversals - Core Logic
Reroot adjusts reversal count
21. Min Edge Reversals - Implementation
Cost delta when moving root
22. Problem - Collect Apples
LC 1443 - collect apples, return home
23. Small-to-Large Merging
The merging technique
24. Collect Apples - Solution
Traverse edge if subtree has apples
25. Collect Apples - Why This Works
2 * edges_with_apples_below
26. Quiz: Tree Techniques
Which tree technique?
27. Quiz: Rerooting DP
When to reroot?
28. Common Mistakes in Tree Problems
Undirected but stored directed
29. Problem - Link Cut Centroids
CF 1406C - fix centroids
30. Link Cut Centroids - Solution
The solution
31. Problem - Tree Requests
CF 570D - subtree queries
32. Tree Requests - Solution
The solution
33. Problem - Kingdom and its Cities
CF 613D - virtual tree
34. Kingdom and its Cities - Solution
The solution
35. Problem - Tree Isomorphism II
CSES - tree structure
36. Tree Isomorphism II - Solution
The solution
37. Problem - Count on a Tree II
SPOJ COT2 - path counting
38. Count on a Tree II - Solution
The solution
39. Section Recap
Rerooting to binary lifting