Graphs & Trees
Bridges, shortest paths, LCA, centroid decomposition, and tree DP through 10 problems.
Lessons
1. Introduction to Advanced Graphs
Beyond basic traversals
2. Techniques Overview
What you'll learn
3. Codeforces 732F Tourist Reform - Problem Statement
CF 732F - maximize min edge-connectivity
4. Codeforces 732F Tourist Reform - Why Naive Fails
Trying all orientations is exponential
5. Tourist Reform - Key Insight
Bridge tree and 2-edge-connected components
6. Codeforces 732F Tourist Reform - Solution
Contract $2$-edge-connected components
7. Codeforces 732F Tourist Reform - Implementation
Bridge finding and component contraction
8. Codeforces 732F Tourist Reform - Example and Complexity Analysis
Linear in graph size
9. Codeforces 652E Pursuit For Artifacts - Problem Statement
CF 652E - path through special edge
10. Codeforces 652E Pursuit For Artifacts - Solution
Query on bridge tree
11. Codeforces 652E Pursuit For Artifacts - Implementation
Bridge tree path query
12. Codeforces 652E Pursuit For Artifacts - Example and Complexity Analysis
Linear preprocessing
13. Codeforces 545E Paths and Trees - Problem Statement
CF 545E - minimum weight shortest path tree
14. Codeforces 545E Paths and Trees - Solution
Greedy edge selection in Dijkstra
15. Codeforces 545E Paths and Trees - Implementation
Modified Dijkstra with tie-breaking
16. Codeforces 450D Jzzhu and Cities - Problem Statement
CF 450D - remove redundant railways
17. Codeforces 450D Jzzhu and Cities - Why Naive Fails
Checking each railway independently
18. Codeforces 450D Jzzhu and Cities - Solution
Track shortest path sources
19. Codeforces 450D Jzzhu and Cities - Implementation
Dijkstra with path counting
20. Codeforces 450D Jzzhu and Cities - Example and Complexity Analysis
Single Dijkstra run
21. Codeforces 786B Legacy - Problem Statement
CF 786B - edges to ranges
22. Codeforces 786B Legacy - Why Naive Fails
Too many edges
23. Legacy - Key Insight
Segment tree as graph nodes
24. Codeforces 786B Legacy - Solution
Segment tree graph
25. Codeforces 786B Legacy - Implementation
Build segment tree graph
26. Codeforces 786B Legacy - Example and Complexity Analysis
Logarithmic edges per operation
27. Codeforces 1051F The Shortest Statement - Problem Statement
CF 1051F - almost-tree shortest paths
28. Codeforces 1051F The Shortest Statement - Why Naive Fails
Dijkstra per query is too slow
29. The Shortest Statement - Key Insight
Near-tree structure exploitation
30. Codeforces 1051F The Shortest Statement - Solution
LCA on tree plus special vertices
31. Codeforces 1051F The Shortest Statement - Implementation
Precompute special vertex distances
32. Codeforces 1051F The Shortest Statement - Example and Complexity Analysis
Leverages sparse extra edges
33. Codeforces 609E Minimum Spanning Tree for Each Edge - Problem Statement
CF 609E - MST containing specific edge
34. Codeforces 609E Minimum Spanning Tree for Each Edge - Solution
Maximum edge on MST path
35. Codeforces 609E Minimum Spanning Tree for Each Edge - Implementation
LCA with max edge tracking
36. Codeforces 609E Minimum Spanning Tree for Each Edge - Example and Complexity Analysis
MST plus LCA queries
37. Codeforces 1495D BFS Trees - Problem Statement
CF 1495D - count valid BFS trees
38. Codeforces 1495D BFS Trees - Solution
Layer by layer counting
39. Codeforces 1495D BFS Trees - Implementation
Product of valid parent counts
40. Codeforces 1495D BFS Trees - Example and Complexity Analysis
Quadratic in vertices
41. Codeforces 771C Bear and Tree Jumps - Problem Statement
CF 771C - sum of jump distances
42. Codeforces 771C Bear and Tree Jumps - Why Naive Fails
Quadratic pair enumeration
43. Bear and Tree Jumps - Key Insight
Modular distance counting for contribution
44. Codeforces 771C Bear and Tree Jumps - Solution
Contribution by distance mod k
45. Codeforces 771C Bear and Tree Jumps - Implementation
Tree DP with mod k tracking
46. Codeforces 771C Bear and Tree Jumps - Example and Complexity Analysis
Linear with small k factor
47. Codeforces 519E A and B and Lecture Rooms - Problem Statement
CF 519E - count equidistant vertices
48. Codeforces 519E A and B and Lecture Rooms - Why Naive Fails
Linear counting per query
49. Codeforces 519E A and B and Lecture Rooms - Solution
Find midpoint via LCA
50. Codeforces 519E A and B and Lecture Rooms - Implementation
LCA with subtree size queries
51. Quiz: Graphs and Trees
Test your understanding
52. Section Recap
What you've learned