Add new edge to graph and find new spanning tree in O(n)

Question

Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.

(c) from Skiena manual

Start Prim or Kruskal alg from u or v until we reach a fragment of the given spanning tree path? Seems the new spanning tree won't change a lot from one new edge.

Answer 1

Determine the path between the endpoints of the new edge in G. If the maximum length edge in that path is greater than that of the new edge, replace it with the new edge. This runs in O(N) time.

Source: Trail Maintenance IOI 2003