Maintain minimum spanning tree as edge weights change. When edge weight decreases:
If edge is in MST, update weight
If not in MST, check if adding it creates a cycle with heavier edge When edge weight increases (edge in MST):
Remove edge from MST
Find minimum edge crossing the cut
Add that edge
Link-Cut trees enable:
- Path maximum query (to find heaviest edge on path)
- Link/cut for MST updates
Time: per update.