Link-Cut Tree

Maintain a forest under link and cut, with path queries and updates, all in $O(\log n)$ amortized. See Sleator-Tarjan Dynamic Trees for the structural details; this page is the practical view.

What it gives you

Operation	Meaning
link(u, v)	add an edge (u must be a root)
cut(u, v)	remove an edge
findRoot(v)	the root of $v$‘s tree
connected(u, v)	same tree?
evert(v)	re-root the tree at $v$
pathQuery(u, v)	aggregate along the path
pathUpdate(u, v, x)	lazy update along the path
lca(u, v)	with a fixed root

The mental model

The forest is split into preferred paths, each stored in a splay tree keyed implicitly by depth. Paths hang off one another by path-parent pointers — one-way links the splay trees themselves do not see.

The single primitive is access(v): make the root-to-$v$ path one preferred path, with $v$ at its bottom. Every other operation is access plus a splay-tree manipulation.

Do you actually need it?

Situation	Better tool
Tree is static, path queries + updates	HLD — simpler, $O({\log }^{2}n)$
Only subtree queries under link/cut	Euler tour tree — simpler
Only connectivity, edges added and removed	offline segment tree on time + rollback DSU
Only connectivity, edges only added	DSU
Everything is offline	almost always something simpler
Online link/cut and path aggregates	link-cut tree

That last row is genuinely narrow. Before writing 200 lines of link-cut tree, spend five minutes checking whether the problem is offline.

When it is the right answer

• Dynamic MST — maintain a spanning forest; on inserting an edge, query the maximum edge on the tree path and swap if the new edge is lighter.
• Online connectivity in a forest — $O(\log n)$ per operation.
• Dinic with dynamic trees — pushing along a whole path in $O(\log n)$ gives $O(nm\log n)$ max flow.
• Maintaining a tree while answering path queries — the defining use.
• LCA in a changing tree.

Implementation notes

The details that break implementations:

1. evert uses a lazy reverse flag on the splay tree. Every push must swap children and propagate the flag; forgetting this in one place corrupts everything.
2. Path-parent pointers are not splay-tree parents. A node’s parent may be either; distinguish with isRoot(v) — true when $v$‘s parent does not list $v$ as a child.
3. push down the whole splay path before splaying. Collect ancestors into a stack, push top-down, then splay.
4. Non-commutative aggregates need both a forward and a reverse value per node, swapped when the reverse flag fires.
5. Subtree aggregates are hard. Link-cut trees natively handle paths. Subtree sums require the “virtual subtree” augmentation, which roughly doubles the code.

Complexity

$O(\log n)$ amortized per operation, via a heavy-light argument on preferred-child changes plus the splay access lemma. Not worst case — a single operation can take $O(n)$ — which matters only for interactive or real-time settings.

Top trees

The generalisation that handles non-path information (subtree aggregates, diameter under link/cut, arbitrary “cluster” merges). More powerful, substantially harder, and essentially never needed in a contest.

See also: Sleator-Tarjan Dynamic Trees · HLD · Euler Tour Trees