You have a forest that changes over time. Edges are added (link) and removed (cut).
You need to answer:
- "Are nodes and in the same tree?"
- "What's the sum/min/max on the path from to ?"
- "What's the root of node 's tree?"
Union-Find handles connectivity but not path queries.
Heavy-Light Decomposition handles path queries but not edge deletions.
Link-Cut trees do everything in amortized:
- Link two trees
- Cut an edge
- Query/update the path between any two nodes
You're implementing the most powerful dynamic tree structure. In this section, I'll show you how it works using splay trees as the backbone.