Binary Lifting - Preprocessing

Here is the implementation. First, preprocess to build the binary lifting table and compute depths. Then use the two-step algorithm to answer queries. The preprocessing computes up[v][i] = $2^i$-th ancestor of v, and depth[v] = distance to root. This takes $O(n \log n)$ time. For each query, level both nodes to the same depth using binary jumps.

Then jump them upward together in decreasing powers of $2$. Stop when they are about to become the same node. At that point, up[u][0] is the LCA. Time: $O(\log n)$ per query after $O(n \log n)$ preprocessing. Space: $O(n \log n)$ for the table. This is the standard approach for LCA in competitive programming when you need to handle many queries.