Link-Cut Tree, in depth: preferred paths, access, make_root and a tested implementation

Preferred paths and path-parent pointers

Take a rooted tree. At each node, mark at most one child as preferred. Following preferred edges partitions the tree into vertex-disjoint preferred paths, each running downward from some node. A link-cut tree stores each preferred path as a splay tree whose in-order sequence is the path from top to bottom. In other words, the splay tree is keyed by depth, not by any stored value.

Paths are connected by path-parent pointers. The root of each splay tree keeps a pointer to the represented-tree parent of its path's topmost node. The parent does not point back. That asymmetry is the whole trick: one par field per node serves as a splay parent when the parent lists the node as a child, and as a path-parent pointer when it does not. A node is the root of its splay tree exactly when its par is empty or its parent lists neither child as it.

Access, the operation everything uses

Every operation starts with access(v). Access makes the path from the tree's root down to v the preferred path, with v as its lowest node, and splays v to the root of that path's splay tree. It walks upward:

1. Splay v within its own splay tree. Drop v's right subtree, which holds the deeper part of v's old preferred path, by setting the right child to nothing. That subtree keeps v as its path-parent automatically, because its root's par is still v but v no longer lists it.
2. Follow v's path-parent pointer to w. Splay w, replace w's right child with the tree just built, and repeat from w.
3. Stop when there is no path-parent. Splay v once more so it is the root of the single splay tree holding root-to-v.

After access, v's splay tree contains exactly the root-to-v path, so v's subtree aggregate is the aggregate of that path. To query an arbitrary path u to v, first make u the root of its represented tree. make_root(u) accesses u and then reverses its splay tree with a lazy flag. Reversing the in-order sequence flips depth order, so u becomes shallowest. Then access v, and v's aggregate covers exactly the u-v path.

It helps to see access as the only place where the structure changes shape. make_root, find_root, link, cut and the path queries do no restructuring of their own beyond one access and a constant number of pointer updates. So when an implementation misbehaves, look first at access, splay and rotate, and only then at the operations built on them. The same split makes testing tractable. If access maintains the invariant that every splay tree's in-order sequence is a downward path, and that every path-parent pointer leads to the parent of that path's top node, the other operations follow almost line by line from their definitions.

The amortized bound comes from two arguments. The heavy-light argument bounds the number of preferred-child changes, and so the number of loop iterations in access, by O(log n) amortized. The splay potential argument shows the splays in one access telescope to O(log n) amortized in total. Together they give O(log n) amortized per operation. Individual operations can take linear time, so this is not a worst-case bound.

A complete implementation

The implementation below stores children, parent pointers, a lazy reversal flag, a node value and a subtree sum in flat arrays, with node 0 as the null sentinel. It handles link, cut, connectivity, path sums and point updates. To aggregate something else, change pull: max needs only the operator changed, while min with argmin needs extra fields.

class LinkCut:
    def __init__(self, n, values):          # nodes 1..n, 0 = null
        self.ch = [[0, 0] for _ in range(n + 1)]
        self.par = [0] * (n + 1)            # splay parent OR path-parent
        self.rev = [False] * (n + 1)
        self.val = [0] + list(values)
        self.agg = [0] + list(values)

    def is_root(self, x):                   # root of its splay tree?
        p = self.par[x]
        return p == 0 or (self.ch[p][0] != x and self.ch[p][1] != x)

    def pull(self, x):
        l, r = self.ch[x]
        self.agg[x] = self.agg[l] + self.val[x] + self.agg[r]

    def push(self, x):
        if self.rev[x]:
            l, r = self.ch[x]
            self.ch[x] = [r, l]
            if l: self.rev[l] = not self.rev[l]
            if r: self.rev[r] = not self.rev[r]
            self.rev[x] = False

    def rotate(self, x):
        p = self.par[x]; g = self.par[p]
        d = 1 if self.ch[p][1] == x else 0
        if not self.is_root(p):             # rewire g only inside one splay tree
            self.ch[g][1 if self.ch[g][1] == p else 0] = x
        self.par[x] = g                     # inherits p's path-parent if p was root
        b = self.ch[x][d ^ 1]
        self.ch[p][d] = b
        if b: self.par[b] = p
        self.ch[x][d ^ 1] = p
        self.par[p] = x
        self.pull(p); self.pull(x)

    def splay(self, x):
        stack, y = [x], x                   # push lazy flags top-down, no recursion
        while not self.is_root(y):
            y = self.par[y]; stack.append(y)
        for y in reversed(stack):
            self.push(y)
        while not self.is_root(x):
            p = self.par[x]
            if not self.is_root(p):
                g = self.par[p]
                zigzig = (self.ch[g][0] == p) == (self.ch[p][0] == x)
                self.rotate(p if zigzig else x)
            self.rotate(x)

    def access(self, x):
        last, y = 0, x
        while y:
            self.splay(y)
            self.ch[y][1] = last            # swap in the new deeper path
            self.pull(y)
            last, y = y, self.par[y]
        self.splay(x)
        return last                         # last path joined: the LCA trick

    def make_root(self, x):
        self.access(x)
        self.rev[x] = not self.rev[x]

    def find_root(self, x):
        self.access(x)
        while True:
            self.push(x)
            if not self.ch[x][0]: break
            x = self.ch[x][0]
        self.splay(x)                       # keeps the amortized bound
        return x

    def connected(self, u, v):
        return u == v or self.find_root(u) == self.find_root(v)

    def link(self, u, v):
        self.make_root(u)
        if self.find_root(v) == u: return False   # would create a cycle
        self.par[u] = v                     # path-parent pointer only
        return True

    def cut(self, u, v):
        self.make_root(u); self.access(v)
        if self.ch[v][0] != u or self.ch[u][1]: return False  # no edge u-v
        self.ch[v][0] = 0; self.par[u] = 0; self.pull(v)
        return True

    def path_sum(self, u, v):               # caller ensures connected(u, v)
        self.make_root(u); self.access(v)
        return self.agg[v]

    def set_value(self, x, value):
        self.access(x); self.val[x] = value; self.pull(x)

Two lines carry most of the subtlety. In cut, after make_root(u) and access(v), the splay tree holds exactly the path u to v with v at the root. An edge u-v exists only if that path has two nodes: u is v's left child and u has no right child. That check makes cut safe on non-edges. In link, u is already the root of its represented tree and of its splay tree, so a single path-parent pointer attaches it, with no splay links changed.

Worked example

Take six nodes with values 1:5, 2:3, 3:8, 4:2, 5:7 and 6:4, and link the edges 1-2, 2-3, 2-4, 4-5 and 5-6.

t = LinkCut(6, [5, 3, 8, 2, 7, 4])
for a, b in [(1, 2), (2, 3), (2, 4), (4, 5), (5, 6)]:
    t.link(a, b)
t.path_sum(3, 6)      # 3-2-4-5-6: 8+3+2+7+4 = 24
t.connected(1, 6)     # True
t.cut(2, 4)           # forest splits into {1,2,3} and {4,5,6}
t.connected(1, 6)     # False
t.path_sum(4, 6)      # 2+7+4 = 13
t.link(3, 5)          # reconnect through a different edge
t.path_sum(1, 6)      # 1-2-3-5-6: 5+3+8+7+4 = 27

Trace path_sum(3, 6). make_root(3) accesses 3, which builds the splay tree for the path from the current root down to 3, then flips it so 3 is shallowest. access(6) then walks from 6 up through path-parent pointers, splicing 5, 4 and 2 into one preferred path ending at 6. When it finishes, 6's splay tree holds exactly 3-2-4-5-6 and its aggregate is 24. All three printed values come from running this code.

Applications

• Online dynamic minimum spanning forest. When edge (u, v, w) arrives and u, v are already connected, find the maximum-weight edge on the u-v path. If it is heavier than w, cut it and link the new edge. Represent each edge as an extra node that carries the weight, and give original vertices a weight of negative infinity, so path-max finds edges.
• Faster max-flow. Sleator and Tarjan introduced dynamic trees to speed up blocking-flow computation. With them, Dinic's algorithm runs in O(VE log V) instead of O(V²E). Most contest and production code still uses plain Dinic, because the constant factors are large.
• Dynamic LCA. With a fixed root and no make_root calls in between, call access(u) and then access(v). The value the second access returns, the last path it joined before reaching the top, is the lowest common ancestor of u and v. That claim was also checked against a naive ancestor walk on random trees.
• Forest connectivity under edge deletions. This works when the graph stays a forest. General graphs with deletions need heavier machinery, such as Holm, de Lichtenberg and Thorup's structure, or an offline divide-and-conquer approach.

Bugs that break real implementations

• Rewiring the grandparent across a path-parent boundary. If p is a splay root, g is its path-parent, and g must not gain a child. Always guard with is_root(p).
• Splaying before pushing. A pending reversal above x swaps which child is left and right. Rotating before pushing it corrupts depth order. Push from the splay root down first.
• Testing for a splay root by par == 0 only. That treats a path-parent pointer as a splay link. Check both of the parent's child slots.
• Linking connected nodes or cutting non-edges. Both silently corrupt the forest unless checked, as above.
• Skipping the final splay in find_root. Correctness holds, but the amortized bound breaks, and adversarial sequences go quadratic.
• Recursion. A recursive push from the root down overflows Python's stack on long paths. Use an explicit stack, as the code does.
• Testing on small cases only. Bugs hide until a reversal meets a rotation at a path boundary. Fuzz against a brute-force forest, which is how the code above was checked.

Trade-offs against other techniques

What to do next

1. Implement the class above and fuzz it against a brute-force forest for at least 10,000 random operations before you trust it.
2. Swap the sum aggregate for max with argmax, and solve online minimum spanning forest using edge-nodes.
3. Add an LCA method that returns the last path-parent target from access, and check it against binary lifting.
4. Measure: time 10⁵ operations in Python, then port to C++ or Rust, and compare.
5. Before you reach for a link-cut tree, check whether union-find, an offline method or heavy-light decomposition already answers the question.

Related reading: union-find for insertion-only connectivity, the Euler tour technique for subtree queries, lowest common ancestor, Dinic's max-flow and treaps, another self-adjusting search tree.