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.