## Editorial for Tree Distance

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

For the first subtask, we can simply run a Breadth-first search (BFS)/Depth first search (DFS) for each query.

Time Complexity: $$\mathcal{O}(QN)$$

For the second subtask, we need a data structure to handle queries in sublinear time (better than $$\mathcal{O}(N)$$).

It turns out that this very particular problem can be solved by finding the lowest common ancestor (LCA) of the $$2$$ nodes. Let $$h[u]$$ denote the height of node $$u$$ in the rooted tree. Thus, for each query, the answer would be $$h[a] + h[b] - 2 \times h[lca(a, b)]$$. The proof is left as an exercise for the reader.

Now, we need a fast way of finding the LCA of $$2$$ nodes. There are many ways of doing this, all of which are $$\mathcal{O}(\log N)$$ or amortized $$\mathcal{O}(\log N)$$ time, which is fast enough to pass.

One such way is utilizing a data structure called a sparse table. Another such way is using an algorithm called Heavy-Light Decomposition. If you want to go overkill, another possible data structure would be a Link/Cut Tree, but this data structure is very complex and will not be taught in our lessons.

Time Complexity: $$\mathcal{O}(Q\log N)$$