Hard Problem from the contest Beginners Special 1.0

Here is the link to this problem: https://www.codechef.com/BGS12020/problems/BSPDP2
Here is the link to my submission:

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.

I have converted my code to online queries now. Here is my new code:

I took a lot of help from this submission: https://www.codechef.com/viewsolution/35218669

If now someone could look at my code and tell how can I optimize it even more, it would really help me. Thanks in advance.

Finally got it accepted xD. Final submission:

Hey, editorials for beginners special 1.0 are out. LINK , You can go though it. sorry for the delay :sweat_smile: