Reveal - Company Queries II

This problem asks for the lowest common ancestor of two employees. No updates, no subtree ranges, no path counting. Ancestor queries.

LCA with Binary Lifting is perfect. You preprocess the tree once in $O(n \log n)$ time, storing ancestors at powers of $2$ for each node. Then each LCA query takes $O(\log n)$.

With $200$,$000$ queries, this runs comfortably within time limits. Naive $O(n)$ per query would TLE.

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