Graph Algorithm Problem that needs explanation :

Recall that a spanning tree of a weighted undirected connected graph is a subset of its edges which form a tree. A spanning tree is minimal (minimum-cost, minimum-weight) if the sum of the weights of its edges is minimal over all spanning trees.

Let G = (V,E) be an (undirected) graph with costs c 0 on the edges e E. Assume you are given a minimum cost spanning tree T in G. Now assume that a new edge is added, connecting two nodes v,w V with cost c.

1. Give an efficient algorithm to test if T remains the minimum cost spanning tree with the new edge added. Make your algorithm run in time O(|E|). Please note any assumption you make about what data structure is used to represent the tree T and the graph G.
2. Suppose T is no longer the minimum cost spanning tree. Give a linear time algorithm to update the tree T to the new minimum cost spanning tree.