Editorial for Tree Distance
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:
For the second subtask, we need a data structure to handle queries in sublinear time (better than ).
It turns out that this very particular problem can be solved by finding the lowest common ancestor (LCA) of the nodes. Let denote the height of node in the rooted tree. Thus, for each query, the answer would be . The proof is left as an exercise for the reader.
Now, we need a fast way of finding the LCA of nodes. There are many ways of doing this, all of which are or amortized 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:
Comments