Link-Cut tree operations are amortized, not worst-case. Potential function argument: Define potential based on "heavy" vs "light" edges in the preferred path decomposition.
Each access changes light-to-heavy edge classifications amortized. Intuition:
- Splaying moves accessed nodes to root, making future accesses faster
- Access changes preferred paths, but each change is "paid for" by the operation causing it
- Over operations, total work is
Single operations can be in worst case, but sequences of operations take total.