Parent Array

When you move from a chain head to its parent during path queries, you need parent[v] for each node. Compute this during the initial tree traversal. For the root, parent[root] = -1 or root itself, depending on your implementation.

For other nodes, parent[v] is set when you visit $v$ from its parent during DFS. This takes $O(n)$ time and $O(n)$ space. The parent array is also used in many other tree algorithms, so it is a standard preprocessing step.

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