Given a tree and Q queries to be answered. In each query you will be provided with 2 nodes u & v. You should return the path, like u -> v1 -> v2... -> v
I have a naive approach to perform DFS for each query but can it be made any better? Is any kind of pre-processing possible? (I'm new to graphs! Kindly help me and also correct me if I went wrong somewhere)
I am assuming that at each tree node you also have the parent node, using which you can go up in the tree as well.
With this assumption, this problem seems to be that of finding the lowest common ancestor. Which is a standard problem, and you can easily find on the net how to solve it.
Once you have the lowest common ancestor your path will be from u--><lowest_common_ancestor>-->v
Just find lowest common ancestor, then further algo will become apparent to you.
If there are no updates you can simply store the path to the root of the tree in each node. Then if you need the way from node a to b the path is represented in this way
a <--> b = a <--> LCA(a, b) + b <--> LCA(a, b)
(you can find the LCA in O(1) time using Sparse Table)
The question is how that this helps you...
See - if you have the path from LCA(a, b) to the root of the tree and the path from a to the root - the path from a to LCA(a,b) is simply
root <--> LCA(a, b) - root <--> a.
Same way to calculate path from LCA(a, b) to b and your path from a to b is the sum of these two.
Whole approach is O(n) time for preprocessing and O(1) for each query if you use sparse table for LCA.
