Problem - Company Queries II

You are given a tree representing company hierarchy. Answer queries: who is the lowest common ancestor (LCA) of two employees?

Euler tour full variant solves this. Record every node during DFS (including revisits). LCA of $u$ and $v$ is the shallowest node between their first occurrences in the tour. Use RMQ (range minimum query) on depths to find LCA in $O(\log n)$ per query after $O(n \log n)$ preprocessing.

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