CONCEPT · Grandmaster
Lowest common ancestor
also binary lifting · LCA
Deepest common node on two root-paths. Binary lifting answers it in O(log n) after O(n log n) setup. Distance is depth[u]+depth[v]-2·depth[lca].
Intuition
Lift the deeper node onto the same level, then climb both until they meet. The 2^k table is just a skip list of parents.
When to reach for it
- CSES Company Queries / Distance Queries
- k-th ancestor
- Path aggregates when combined with an Euler tour + Fenwick
Usual pits
- parent[root] = -1 then indexing it
- Walking parent one-by-one at n,q=2e5
- Forgetting to build depth[] with a DFS first