Link-Cut Tree

The dynamic-tree problem

Static trees are easy. Build them once; precompute LCA tables, sparse tables, Euler tours; answer queries in O(log n) or even O(1). But many graph algorithms — max flow, online minimum spanning tree, articulation-point maintenance — modify the tree as they run. Add an edge here, remove one there, ask "what's the sum of capacities along the path from s to t" between every modification. With ordinary tree traversal, each query is O(depth), each edit is O(1), and any cap-restoration walk over a long path costs linear time. The total runtime balloons.

A link-cut tree solves this in O(log n) amortized per operation, regardless of the tree's depth. The structure represents not the tree directly, but a decomposition of the tree into easier-to-update pieces.

Preferred paths — the key idea

For each internal node v, designate exactly one of v's child edges as the preferred edge. The choice is dynamic: the preferred edge of v is the one most recently used in a path traversal from somewhere in the tree to a descendant of v.

Preferred edges connect into preferred paths — vertex-disjoint chains running from some "top" node down to a leaf. Every node lies on exactly one preferred path. A tree of n nodes has at most n preferred paths (one per leaf, give or take); typically O(log n) preferred paths cross the path from any specific node to the root, on average across long access sequences.

Each preferred path is stored in its own auxiliary structure — typically a splay tree keyed by depth. The shallowest node in the preferred path is the leftmost node of the splay tree; the deepest is the rightmost. The splay tree is rotated under standard splay rules; depth becomes the "key" implicitly.

The access operation

Every link-cut operation begins with access(v), which ensures v's preferred path runs from the tree's actual root all the way down to v. The procedure:

1. Splay v in its auxiliary splay tree. Now v is the root of that splay tree.
2. If v has a right subtree in the splay tree, it represents v's "deeper" preferred-path nodes. Detach that subtree — it becomes a separate preferred path.
3. Walk to the parent of v's preferred path (called the "path-parent pointer"). This is the node above v's path in the original tree.
4. Splay the path-parent in its auxiliary tree.
5. Attach v's splay tree as the path-parent's right subtree — merging the two preferred paths.
6. Repeat until the path-parent pointer is null (we've reached the represented tree's root).

After access, v is at the bottom of a single preferred path that begins at the root. All four core operations now reduce to manipulating this exposed path.

Operations in detail

• find_root(v). access(v); the leftmost node of v's auxiliary splay tree (the shallowest) is the root. Splay it to the top of the splay tree, return it. O(log n) amortized.
• link(u, v). Precondition: u is a tree root, v is in a different tree. access(u) and access(v). u's auxiliary splay tree has no left subtree (u is the shallowest, since u is a root). Attach v's splay tree as u's left subtree. O(log n) amortized.
• cut(v). access(v). v's preferred path now goes from root down to v. The left subtree of v in the auxiliary splay tree contains everything strictly above v in the actual tree. Detach the left subtree — it becomes a separate tree (the original tree minus v's subtree). v's right subtree plus v itself form v's subtree's new representation. O(log n) amortized.
• path_query(v, op). access(v). The auxiliary splay tree at v now stores the entire root-to-v path. Aggregate the splay tree's nodes using op (sum, min, max) — store the aggregate at each node and combine lazily. O(log n) amortized.
• lca(u, v). access(u), then access(v). The last preferred-path switch during access(v) lands on the LCA — return that node. O(log n) amortized.

Worked example: max flow speedup

Suppose we run Dinic's algorithm on a graph with |V| = 100, |E| = 5000. Naive Dinic finds blocking flows in O(VE) = 500,000 per phase, with at most V phases = 50 million total operations. With link-cut trees, finding a min-capacity edge along an augmenting path costs O(log 100) ≈ 7 instead of O(V) = 100; subtracting that capacity from every edge along the path costs another O(log V) via path-update; cutting saturated edges costs O(log V) each. Each blocking flow runs in O(E log V) = 5000 * 7 = 35,000 ops. Total Dinic cost: O(VE log V) = 3.5 million — a 14× speedup. For larger graphs the speedup grows; on V = 10^4, E = 10^6, link-cut Dinic is ~80× faster.

Alternatives and variants

	Link-cut tree	Euler-tour tree	Top tree
Path queries	O(log n) natural	O(log n) via lazy prop	O(log n) natural
Subtree queries	O(log n) with augmentation	O(log n) natural	O(log n) natural
Implementation lines	~300 C++ lines	~200 C++ lines	~600 C++ lines
Constant factor	Low	Medium	High
Inventor / year	Sleator-Tarjan 1983	Henzinger-King 1995	Alstrup et al. 1997
Best for	Path-heavy workloads	Subtree-heavy workloads	Generic dynamic tree
Used in	Max flow, online MST	Dynamic connectivity	Theoretical work

For competitive programming, link-cut tree is the default. Top trees are simpler to analyze but heavier to code. Euler-tour trees lose to link-cut on path-heavy queries and are usually only chosen when subtree-only operations dominate.

Where link-cut trees ship

• Max-flow. Sleator-Tarjan Dinic, Goldberg-Tarjan push-relabel — both gain log-factor speedups from link-cut underneath.
• Online MST. Maintain a minimum spanning forest under edge insertion and deletion. Each edit calls link or cut on the link-cut tree; path queries find the heaviest edge on a cycle.
• Dynamic articulation / bridge points. 2-edge-connectivity maintenance in O(log^2 n) per update — uses link-cut as a primitive.
• Competitive programming. "Dynamic tree" problems on Codeforces, AtCoder, ICPC. Path-sum, path-XOR, path-max queries with link/cut updates.
• Network simulators. ns-3 and similar tools use link-cut variants for fast routing-table maintenance in dynamic topologies.

Implementation notes

• Path-parent pointer. Each auxiliary splay tree's root carries a pointer to its parent in the actual tree (not the splay tree). On splay, this pointer rides with the new root. This is the one source of bugs in 90% of implementations.
• Reverse flag for makeroot. Many problems want makeroot(v) — re-root the tree at v. Implement with a "reverse" lazy flag on each splay node: flipping the flag swaps left and right of the entire subtree.
• Subtree aggregates. Storing subtree sums requires augmenting each node with virtual_subtree_sum (sum of all non-preferred-children's subtree-sums). Adds bookkeeping on link/cut/access.
• No recursion. Splay and access can be implemented iteratively. Some competitive-programming templates do recursion; production code uses iteration to avoid stack overflows on long chains.
• Common pitfall. Always splay v after access(v) — failing to do this works for correctness but breaks the amortized analysis, leading to TLE on adversarial inputs.

Amortized analysis — two layers deep

The analysis has two layers stacked on top of each other.

Layer 1 — splay amortized. Each auxiliary splay tree, by Sleator-Tarjan's access lemma, gives O(log n) amortized per operation on that splay tree. This handles the cost of moving within a single preferred path.

Layer 2 — preferred-path switches. The cost of access(v) is bounded by (number of preferred-path switches on access) * O(log n) splay-tree work per switch. Sleator and Tarjan prove a heavy-path-style bound: over any sequence of m accesses on an n-node tree, the total number of preferred-path switches is O(m log n). Amortized per access: O(log n) switches.

Combining: each access does O(log n) switches, each switch is O(log n) splay work… but wait, that's O(log^2 n)! Indeed, the simpler heavy-light variant gives O(log^2 n) per operation. The optimization to O(log n) requires a more careful potential function (Sleator-Tarjan 1985 "Self-Adjusting Binary Search Trees" + the 1983 link-cut paper combined). Most coding-competition templates implement the O(log^2 n) variant because it's simpler and the log factor is rarely the bottleneck in practice.

Common misconceptions

• "Link-cut trees are red-black or AVL underneath." No — the auxiliary trees are splay trees specifically. The amortized analysis depends on splay's access-lemma properties; red-black or AVL would break the bound.
• "You can store path information in node fields." No — each operation needs path aggregates that combine across the splay structure. Aggregates live on the splay nodes and are recomputed on every rotation.
• "Cut is just delete an edge." Not quite — cut(v) detaches v and its entire subtree from v's parent, but you must first call access(v) to expose the right structure inside the auxiliary splay tree.
• "Path-query is O(log n) trivially." The path-aggregate cost is O(log n) amortized only because we splay during access. Without splay, you'd walk down the path naively for O(depth) per query — exactly the problem we set out to solve.
• "Link-cut trees work for unrooted trees." Direct link-cut assumes rooted trees. For unrooted, use makeroot(v) (with the reverse flag) to re-root before each operation. Adds amortized cost but stays O(log n).