Company Queries II - Implementation

Preprocessing: same as Problem I (build $up$ table, compute $depth$).

Query $(a, b)$:

if depth[a] < depth[b]:
 swap(a, b)
diff = depth[a] - depth[b]

for j = 0 to log(n):
 if diff & (1 << j):
 a = up[a][j]

if a == b:
 return a

for j = log(n) down to 0:
 if up[a][j] != up[b][j]:
 a = up[a][j]
 b = up[b][j]

return up[a][0]

Binary lifting uses preprocessing to speed up tree queries. You build a table of exponential ancestors, then use binary decomposition to jump efficiently. This technique appears in many graph problems. Understanding it now will help you solve LCA, path queries, and distance problems later.

This runs in $O(n \log n)$ time and uses $O(n \log n)$ space.