## Editorial for Tree Distance

**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:

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)\)

## Comments