Here is the link to this problem: https://www.codechef.com/BGS12020/problems/BSPDP2
Here is the link to my submission:
https://www.codechef.com/viewsolution/35222588
To solve this problem, I did the following:
I took all the queries as the input first of all and stored all of them. Then with the queries which required me to add an edge, I just added the edges. In the end, I had a tree with me with the queries of the shortest path still remaining to be processed. For this I used the concept of LCA and found the distance between two nodes u and v by the following formula: dist[root-u]+dist[root-v]-2*dist[root-lca(u,v)]
Now, with this solution, I am pretty sure that the time complexity is O(QlogN). I am still getting a TLE in it. If someone else also solved this question using the same logic and got accepted, can you please look at my solution and tell me what have I done wrong in it. Thanks in advance.
