Добавить новое ребро в граф и найти новое остовное дерево в O (n)

Предположим, нам дано минимальное остовное дерево T данного графа G (с n вершин и m ребер) и новое ребро e = (u, v) веса w, которое мы добавим к G. Приведите эффективный алгоритм поиска минимального остовного дерева графа G + e. Ваш алгоритм должен работать за O (n) время, чтобы получить полный кредит.

(c) из руководства Skiena

Начать Prim или Kruskal alg с u или v, пока мы не достигнем фрагмента данного пути связующего дерева? Похоже, новое остовное дерево не сильно изменится по сравнению с одним новым ребром.