Lowest Common Ancestor

By the end, you can

• Define LCA and explain why "a node is its own ancestor" matters for edge cases.
• Apply the formula dist(u,v) = depth[u] + depth[v] − 2·depth[lca] to compute tree distances.
• Build the binary-lifting table using the doubling recurrence and read off any 2^k-th ancestor.
• Trace through a binary-lifting LCA query: equalize depths, jump together skipping jumps that overshoot, and return the parent as the final answer.
• Explain why the loop stops one step below the LCA and returns `up[u][0]`.
• Compare binary lifting, Euler-tour RMQ, and Tarjan's offline method by their preprocessing and per-query costs.
• Identify when Tarjan's offline algorithm is advantageous (all queries known in advance).