Need help with this problem:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=6218

My solution: https://paste.ubuntu.com/p/Sx7gYY5syf/

Verdict: TLE

I used Sparse Table for the LCA and Kruskal for the MST. My actual code starts from line 117, the rest above is template, can be ignored. I commented in each step to explain what I did.

My idea for the solution: I construct MST from the given graph. This way I only repair the roads that yield minimum cost and connects all the cities. Then, for each query, if the given road is already in the MST, we just construct the rest of the roads in the MST. Hence we return the sum of all edges in the MST. Else, if the road is not in the MST, we remove the most costly road (largest weighted edge) along the path from u to v from the MST, and add the given road.