~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Binary lifting / LCA
up[k][v] = 2^k-th ancestor; LCA and k-th ancestor in O(log n).
Notes
Recognise it when: you need the k-th ancestor, the LCA with many queries, or "jump 2^k steps" in a functional graph.
up[0][v] = parent, up[j][v] = up[j-1][ up[j-1][v] ]. For the k-th ancestor, take the set bits of k. For the LCA, lift the deeper node to the same depth, then lift both while up[j][a] != up[j][b].
O(n log n) preprocessing and O(log n) per query.
4 problems
Advanced & competitive
Tree techniques Binary lifting, LCA, Euler tours.
Binary lifting / LCA
- Basics: build the jump table basics py · c++ · java easy
- Earliest ancestor born since a year py · c++ · java easy
- K-th ancestor queries py · c++ · java medium
- Lowest common boss py · c++ · java medium