Link-Cut Tree — Dynamic Tree Operations

Preferred path decomposition

Each node has one 'preferred' child. Preferred paths represented as splay trees keyed by depth.

Operations

void link(u, v) { access(v); makeRoot(u); attach u to v's root; }
void cut(u, v) { access(u); split from parent; }
auxiliary access(u) { splay u to root, do path traversal to global root }

Path aggregate

access(u) brings u's preferred path to root of its splay. Then query the splay for path aggregate.

Complexity

All operations O(log N) amortized. Analysis via heavy-path decomposition + splay's amortized bound.