Core Idea - LCA via Euler Tour

Full Euler tour creates sequence where each node appears multiple times. Between the first occurrence of $u$ and first occurrence of $v$, the node with minimum depth is their LCA. Build array depth[i] = depth of node at position $i$ in tour.

Build RMQ structure (segment tree or sparse table) on $depth$. For LCA query: find positions first[u] and first[v] in tour, query RMQ on range between them, return the node at the position with minimum depth.