Euler Tour + RMQ - Full Algorithm

Preprocessing: Build the Euler tour with first[v] and tourDepth arrays. Then build a sparse table on tourDepth. Query: For lca(u, v), let l = first[u] and r = first[v]. If l > r, swap them. Query the sparse table for the index with minimum depth in $[l, r]$. That index points to the LCA node. This combines two effective techniques: Euler tour converts the tree to an array, and sparse table answers range queries in $O(1)$ time.

The result: $O(n \log n)$ preprocessing, $O(1)$ per query. This is a practical online LCA algorithm for static trees. Farach-Colton and Bender's method achieves $O(n)$ preprocessing with $O(1)$ queries, but this sparse table approach is simpler to implement.

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