Link-Cut Tree

Dynamic forest · preferred-path decomposition · access(v) re-splays the root-to-v path

access O(log n) link O(log n) cut O(log n) amortized

Represented forest (solid = preferred path · dashed = path-parent)

Preferred path 1
Preferred path 2
Preferred path 3+
path-parent (virtual)
active node

Controls

slow fast

Step explanation

Pick a node v and press access(v) to expose the root-to-v path as one preferred path.
nodes: 0
preferred paths: 0
last op: —
pref-child changes: 0

Big-O (amortized)

OperationTimeNote
access(v)O(log n)core; everything routes through it
link(u,v)O(log n)makeRoot + set path-parent
cut(u,v)O(log n)access + splice
findRoot(v)O(log n)access + walk-left
makeRoot(v)O(log n)access + lazy reverse
path aggregateO(log n)read splay-root field
spaceO(n)O(1) fields per node

Operation log