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.