Graph Theory37 sections · 1633 units
Open in Course

Why This Works

(Jump as far as possible)

You want to jump as far as possible without overshooting the LCA. By checking up[a][j] != up[b][j], you ensure the jump does not merge the paths. If up[a][j] = up[b][j], jumping would land both at the same node or above the LCA. So you skip that jump. By trying all powers of 22 from largest to smallest, you get as close to the LCA as possible.

One more step brings you to the LCA. This greedy approach works correctly because the jumps are independent.