233. In a rooted DAG (or a tree), how do you find the lowest common ancestor or shortest ancestral path of two vertices?
HardGraph algorithms
Technical
Show model answer
An ancestral path between v and w goes up from v to a common ancestor a and up from w to the same a. Run BFS from v and BFS from w along parent (ancestor) edges, recording distances. Every vertex reached by both is a common ancestor; choose the one minimizing distV[a] + distW[a]. Cost O(V + E) per query, and you can stop early once the current BFS levels exceed the best total found.
In a tree the LCA is unique: with parent pointers and depths, lift the deeper node until depths match, then lift both until they meet, O(h). For many queries use binary lifting (O(n log n) preprocessing, O(log n) per query) or an Euler tour plus a sparse-table range-minimum query for O(1) queries.