This problem, despite what it may look like, is not an MST problem.

For the first subtask, the bounds were low enough that one could precompute the shortest distances between any pair of vertices using an algorithm like Floyd-Warshall.

For the second subtask, since the graph is actually a tree, we can store a sparse table of every vertex and its ~2^d~th ancestors, which allows us to answer shortest path queries between two vertices in ~\mathcal O(\log N)~ time.

For the third subtask, we have a tree plus one additional edge. The shortest path may either use the edge or not. In the former case, we want the shortest path from the starting vertex to one vertex in the edge - then we traverse the edge, and we use the tree to head to the destination vertex.

For the last two subtasks, we'll define the graph to be a spanning tree plus some non-tree edges. Every edge that is in the spanning tree will be called a tree edge. Finding a spanning tree can be done in linear time using DFS - we do not necessarily need to find a minimum spanning tree. Define a vertex to be special if it is incident on a non-tree edge.

The fourth subtask can be solved by computing all special vertices and using Dijkstra to compute the shortest path between that vertex and all other vertices in the graph. Answering a query now requires either using only the edges in the spanning tree, or using one special vertex as an intermediary. We loop over all special vertices when answering a query.

For full credit, we need to optimize away the Dijkstra from above. Recall that the shortest path in a rooted tree ascends and then descends, and we will leverage this. We'll start by computing, for every special vertex, the shortest distance to every other special vertex. We can do this in cubic time by considering just the non-tree edges and shortest paths only on the tree edges, and then run Floyd-Warshall. Now, assuming an arbitrary rooting of the spanning tree, we traverse the tree from bottom up to compute the shortest path from every vertex to every special vertex, assuming that you can only go down the tree edges. Finally, we then traverse the tree top-down to relax these paths assuming you can go down tree edges. This computation removes the log factor.