Application: Dynamic MST

Maintain minimum spanning tree as edge weights change. When edge $(u, v)$ weight decreases:

$1.$ If edge is in MST, update weight

$2.$ If not in MST, check if adding it creates a cycle with heavier edge When edge weight increases (edge in MST):

$1.$ Remove edge from MST

$2.$ Find minimum edge crossing the cut

$3.$ Add that edge

Link-Cut trees enable:

• Path maximum query (to find heaviest edge on path)
• Link/cut for MST updates

Time: $O(\log n)$ per update.