Path to LCA Structure

Any path from $u$ to $v$ splits into two parts: the path from $u$ up to $lca(u, v)$ and the path from $lca(u, v)$ down to $v$. Both parts go up, from $u$ to $lca$ and from $v$ to $lca$. Each part is a path from a node up to an ancestor. By the chain property, each part crosses $O(\log n)$ chains.

The full path crosses $O(\log n)$ chains total. To query a path, you walk up from $u$ to the LCA and from $v$ to the LCA, querying each chain segment you touch. You combine all the segment results.

Space complexity is $O(n)$ for the data structures used.