Sleator-Tarjan Dynamic Trees

Purpose: Maintain a forest under link and cut, supporting path queries and updates in $O(\log n)$ amortized. Better known as link-cut trees — Sleator and Tarjan, 1983.

Operations

Operation	Meaning
makeTree(v)	create a single-vertex tree
link(u, v)	attach tree of $u$ (as root) under $v$
cut(v)	detach $v$ from its parent
findRoot(v)	root of $v$‘s tree
pathAggregate(u, v)	sum / min / max along the path $u\to v$
pathUpdate(u, v, x)	add $x$ to every edge on the path
lca(u, v)	lowest common ancestor
evert(v)	make $v$ the root (reverse a path)

All $O(\log n)$ amortized.

The Structure: preferred paths + splay trees

1. Decompose the tree into preferred paths — vertex-disjoint downward paths covering every vertex (like HLD, but the decomposition changes dynamically with access patterns).
2. Store each preferred path in a splay tree, keyed implicitly by depth.
3. Link the splay trees together with path-parent pointers: the root of one path’s splay tree points to the vertex it hangs off in the parent path (a one-way pointer, invisible to the splay tree itself).

access(v) — the one primitive

Everything is built on access(v), which makes the path from the root to $v$ a single preferred path with $v$ at its bottom:

access(v):
    splay(v)
    detach v's right subtree (deeper vertices leave the preferred path)
    while v has a path-parent w:
        splay(w)
        replace w's right subtree with v's splay tree
        rotate v up

Then:

• findRoot(v) = access(v), then walk left to the shallowest vertex;
• pathAggregate(u,v) = evert(u), access(v), read the splay tree’s aggregate;
• link(u,v) = evert(u), then set $u$‘s path-parent to $v$;
• cut(v) = access(v), detach the left subtree.

Complexity

$O(\log n)$ amortized per operation. The proof uses a heavy-light argument to bound the number of preferred-child changes at $O(\log n)$ per access, plus the splay tree access lemma. It is not worst-case: a single operation can cost $O(n)$, though a sequence of $m$ cannot cost more than $O(m\log n)$.

Link-cut trees vs the alternatives

Structure	Handles	Path aggregates	Difficulty
HLD + segment tree	static tree	yes	moderate
Euler tour tree	link/cut	subtree only	moderate
Link-cut tree	link/cut	yes	hard
Top tree	link/cut	yes, plus non-local info	very hard

Do you actually need it?

If the tree is static, use HLD — simpler, worst-case $O({\log }^{2}n)$, and the segment tree gives you lazy updates for free. If updates are offline, consider offline dynamic connectivity instead. Reach for link-cut trees when the tree genuinely changes online and you need path queries.

What it unlocks

• Dynamic connectivity in forests — $O(\log n)$ per operation
• Max flow speedups — Dinic with link-cut trees is $O(nm\log n)$; see Goldberg-Tarjan
• Online MST maintenance — path-max query plus edge swap
• LCA in a changing tree
• Offline problems in disguise — sometimes it is the only structure that fits

Variants / Use Cases

• Link-Cut Tree — the topic page with implementation notes
• Euler Tour Trees — for subtree, not path, aggregates
• Top trees / topology trees — the more general framework
• Splay trees — the self-adjusting BST underneath; Sleator and Tarjan invented those too