The problem is as follows:
Given an edge and a graph, calculate the weight of MST over all spanning trees that contains the given edge. The MST can be found by running Prim's algorithm starting with this edge included. But this query is asked for multiple edges for the same graph so a more efficient algorithm is required (each of them is calculated independently).
The solution for this problem is to first find a MST for the graph and for each given edge calculate the maximum weight of the edges in the cycle that results from adding this edge. the result would be
new weight = old weight + d(u, v) - max weight. What is the proof of correctness for this algorithm?