How to index a tree to allow efficient search for paths?
Root the tree in an arbitrary fashion. Given two nodes $x,y$, let $x_0 = x, x_1, \ldots$ and $y_0 = y, y_1, \ldots$ be the paths going up the tree all the way to the root. If $x_i = y_j$ then the unique path between $x$ and $y$ is $x_0,\ldots,x_i=y_j,\ldots,y_0$.
In order to find this path quickly (at the cost of a little bit of memory), generate the two paths in parallel, $x_0,y_0,x_1,y_1,x_2,y_2,\ldots$, storing the resulting vertices in a hash table, until they collide. This happens at time $\max(i,j)$, which is the same as the path length $i+j$ up to constant factors.

While the description above suggests that you have to store the entire tree ahead of time, this is not necessarily the case. In general, all you need to do is to have a consistent way of determining which of the neighbors of a given vertex is its parent. Whether this is possible without storing the entire tree depends on the problem. When it is possible, you can generate the tree &quot;as you go&quot;, which prompts us to reduce the space complexity of the algorithm (perhaps you don't need to store the path from $x$ to $y$, but only to generate it vertex by vertex).

If space is at premium, you can save a factor of $k$ by storing only a $k$'th fraction of the vertices. Say that a vertex is ($k$-)special if the hash of its index is divisible by $k$. Perform the search as above, but only store special vertices. On average, this will cut the number of vertices stored by a factor of $k$. However, it doesn't give you the exact intersection point. Suppose that your sequences contain the special points $x_{i_1},\ldots,x_{i_a}$ and $y_{j_1},\ldots,y_{j_b}$, where $x_{i_a} = x_{j_b}$. To find the exact intersection point, it suffices to consider the small parts $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$.
If space is still at premium, you can use exponential search followed by binary search. We go over $k=1,2,4,8,\ldots$, and for each value of $k$, determine only the first $k$-special vertex after the initial vertices $x,y$. Suppose that for some $k$, these special vertices coincide. Now generate the sequence of $k/2$-special vertices, until they coincide. Let $x_{i_a}=y_{j_b}$ be the first time these sequences coincide. Then we can narrow the search down to $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$. Now we generate the sequence of $k/4$-special vertices, starting at $x_{i_{a-1}+1},y_{j_{b-1}+1}$ (unless these vertices are the same, in which case we are done); and so on. The running time is still linear, but the space requirements is down nearly to a constant (in expectation).
We can get the space down to a deterministic constant by defining special in terms of the depth of a vertex rather than in terms of its index, but depth is not necessarily easy to compute.