Intro

You have a forest that changes over time. Edges are added (link) and removed (cut).

You need to answer:

• "Are nodes $u$ and $v$ in the same tree?"
• "What's the sum/min/max on the path from $u$ to $v$?"
• "What's the root of node $u$'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 $O(\log n)$ 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.