Problem - Company Queries II

You are given a tree representing a company hierarchy. Each employee except the boss has exactly one direct supervisor. The tree is rooted at the boss. Answer queries: what is the lowest common ancestor of employees a and b?

In other words, who is their closest common supervisor in the hierarchy?

There are up to $200$,$000$ employees and $200$,$000$ queries. You need fast lookups. Binary lifting gives you $O(\log n)$ per query after $O(n \log n)$ preprocessing.