Depth Array

To decide which of $u$ or $v$ is deeper during path queries, precompute depth[v] for each node. The root has depth[root] = 0, and depth[child] = depth[parent] + 1. During path queries, always move the node with greater depth.

This ensures you do not overshoot the LCA. Both nodes gradually move up until they meet. Computing depths takes $O(n)$ time in a single DFS. You can compute depth, parent, and subtree size in the same DFS to save time.

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