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)


There are no comments at the moment.