Algorithm

$1.$ Compute depth[v] for all nodes (BFS/DFS).\n\n$2.$ Build the $up$ table.\n\n$3.$ For query $(a, b)$: if depth[a] < depth[b], swap them.\n\n$4.$ Jump $a$ up to the same depth as $b$: jump depth[a] - depth[b] steps.\n\n$5.$ If $a = b$, return $a$ (one is ancestor of the other).\n\n$6.$ Binary search: for $j = \log n$ down to $0$, if up[a][j] \!= up[b][j], jump both.\n\n$7.$ Return up[a][0] (the LCA).\n\nThis runs in $O(n \log n)$ time and uses $O(n \log n)$ space.