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)$ ~\mathcal{O}(QN)~

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

It turns out that this very particular problem can be solved by finding the lowest common ancestor (LCA) of the $2$ ~2~ nodes. Let $h[u]$ ~h[u]~ denote the height of node $u$ ~u~ in the rooted tree. Thus, for each query, the answer would be $h[a] + h[b] - 2 \times h[lca(a, b)]$ ~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$ ~2~ nodes. There are many ways of doing this, all of which are $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ or amortized $\mathcal{O}(\log N)$ ~\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)$ ~\mathcal{O}(Q\log N)~

Comments

There are no comments at the moment.