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


Comments

There are no comments at the moment.