https://cp-algorithms.com/graph/lca.html
Before answering the queries, we need to preprocess the tree. We make a DFS traversal starting at the root and we build a list $\text{euler}$ which stores the order of the vertices that we visit (a vertex is added to the list when we first visit it, and after the return of the DFS traversals to its children). This is also called an Euler tour of the tree. It is clear that the size of this list will be $O(N)$ .
We also need to build an array $\text{first}[0..N-1]$ which stores for each vertex $i$ its first occurrence in $\text{euler}$ .
Also by using the DFS we can find the height of each node (distance from root to it) and store it in the array $\text{height}[0..N-1]$ .
LCA(v1,v2):
Consider the vertices that we visit in the Euler tour between the first visit of $v_1$ and the first visit of $v_2$ .
the $\text{LCA}(v_1, v_2)$ is the vertex with the lowest height on this path
So the $\text{LCA}(v_1, v_2)$ can be uniquely determined by finding the vertex with the smallest height in the Euler tour between $\text{first}(v_1)$ and $\text{first}(v_2)$ .
-> RMQ problem (finding the minimum in an range)
