Run DFS recording full tour: add when entering and when returning from each child.
Store depth of each node in the tour.
Record first[v] = first position of in the tour.
Build RMQ structure on the depth array (sparse table for query or segment tree for ).
For LCA(, ): query RMQ on range [min(first[u], first[v]), max(first[u], first[v])], return node at the position with minimum depth. Preprocessing: . Query: with sparse table or with segment tree.
Space complexity is for the data structures used.