Full Tour Variant

I record every visit in the full tour, including the return steps. For a tree with edges $(1, 2)$, $(2, 4)$, and $(1, 3)$, the tour is $[1, 2, 4, 2, 1, 3, 1]$. This produces an array of length $2n-1$.

You can answer lowest common ancestor (LCA) queries by taking the node with minimum depth between the first visits of $u$ and $v$ in the tour. Store the depth alongside each visit and run a range minimum query (RMQ) on that depth array. With a sparse table, preprocessing is $O(n \log n)$ time and $O(n \log n)$ space, and each query is $O(1)$ time.