Link-Cut Tree: Dynamic Tree Structure

Key Insights

Link-Cut Trees maintain dynamic forests with O(log n) amortized time per operation, enabling efficient edge insertions, deletions, and path queries on trees that change over time.
The key insight is representing preferred paths as splay trees, where the access operation restructures the tree to make any node-to-root path efficient to query.
Unlike Heavy-Light Decomposition which requires rebuilding after structural changes, Link-Cut Trees handle dynamic connectivity naturally, making them essential for problems involving evolving graph structures.

Introduction to Dynamic Trees

Static tree algorithms assume your tree never changes. In practice, trees change constantly. Network topologies shift as links fail and recover. Game engines need to reparent scene graph nodes. Compilers restructure ASTs during optimization passes.

The dynamic tree problem asks: can we maintain a forest of trees under edge insertions (link) and deletions (cut) while efficiently answering path queries? Heavy-Light Decomposition handles path queries beautifully but falls apart when edges change—you’d need O(n) time to rebuild the decomposition after each modification.

Link-Cut Trees, introduced by Sleator and Tarjan in 1983, solve this elegantly. Every operation—link, cut, path query, path update—runs in O(log n) amortized time. The data structure powers solutions to dynamic connectivity, maximum flow algorithms (particularly in network simplex), and competitive programming problems involving changing tree structures.

Core Concepts: Preferred Paths and Splay Trees

Link-Cut Trees decompose the represented tree into vertex-disjoint paths called preferred paths. Each node has at most one preferred child—the child most recently accessed. The preferred path from any node extends downward through preferred edges until reaching a leaf or a node with no preferred child.

Here’s the critical insight: we represent each preferred path as a splay tree, keyed by depth. Nodes higher in the represented tree appear to the left in the splay tree. This gives us a forest of splay trees (the auxiliary trees) that collectively represent our actual forest.

Each node maintains two types of parent pointers:

Tree parent: standard splay tree parent within the auxiliary tree
Path-parent: points to the parent in the represented tree when that edge is not preferred

struct Node {
    Node* parent;      // Parent in auxiliary splay tree (null if splay root)
    Node* left;        // Left child in splay tree (shallower in represented tree)
    Node* right;       // Right child in splay tree (deeper in represented tree)
    Node* pathParent;  // Path-parent pointer (connects splay trees)
    
    long long value;   // Node value for aggregation
    long long pathSum; // Sum of values in subtree
    bool reversed;     // Lazy reversal flag for makeRoot operations
    
    Node(long long val = 0) 
        : parent(nullptr), left(nullptr), right(nullptr), 
          pathParent(nullptr), value(val), pathSum(val), reversed(false) {}
    
    bool isRoot() {
        return parent == nullptr || 
               (parent->left != this && parent->right != this);
    }
    
    void push() {
        if (reversed) {
            std::swap(left, right);
            if (left) left->reversed ^= true;
            if (right) right->reversed ^= true;
            reversed = false;
        }
    }
    
    void pull() {
        pathSum = value;
        if (left) pathSum += left->pathSum;
        if (right) pathSum += right->pathSum;
    }
};

The isRoot() check is subtle but essential. A node is a splay tree root if it has no parent, or if its parent doesn’t recognize it as a child (meaning the connection is via path-parent, not a tree edge).

The Access Operation

The access(v) operation is the heart of Link-Cut Trees. It restructures preferred paths so that v and the root of v’s represented tree lie on the same preferred path, with v at the bottom. After access, v becomes the root of its auxiliary splay tree.

The algorithm walks up path-parent pointers, splaying at each step and switching preferred children:

void rotate(Node* x) {
    Node* p = x->parent;
    Node* g = p->parent;
    
    bool isRight = (p->right == x);
    Node* c = isRight ? x->left : x->right;
    
    // Update grandparent connection
    if (g) {
        if (g->left == p) g->left = x;
        else if (g->right == p) g->right = x;
    }
    if (p->pathParent) {
        x->pathParent = p->pathParent;
        p->pathParent = nullptr;
    }
    
    x->parent = g;
    p->parent = x;
    
    if (isRight) {
        x->left = p;
        p->right = c;
    } else {
        x->right = p;
        p->left = c;
    }
    
    if (c) c->parent = p;
    
    p->pull();
    x->pull();
}

void splay(Node* x) {
    // Push lazy flags down the path first
    std::vector<Node*> path;
    for (Node* n = x; !n->isRoot(); n = n->parent) {
        path.push_back(n->parent);
    }
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        (*it)->push();
    }
    x->push();
    
    while (!x->isRoot()) {
        Node* p = x->parent;
        if (!p->isRoot()) {
            Node* g = p->parent;
            g->push(); p->push(); x->push();
            // Zig-zig or zig-zag
            bool zigzig = (g->left == p) == (p->left == x);
            if (zigzig) rotate(p);
            else rotate(x);
        }
        rotate(x);
    }
    x->push();
}

Node* access(Node* v) {
    splay(v);
    
    // Detach right subtree (deeper nodes) - they're no longer on preferred path
    if (v->right) {
        v->right->pathParent = v;
        v->right->parent = nullptr;
        v->right = nullptr;
        v->pull();
    }
    
    Node* last = v;
    
    // Walk up path-parent pointers
    while (v->pathParent) {
        Node* pp = v->pathParent;
        splay(pp);
        
        // Switch preferred child
        if (pp->right) {
            pp->right->pathParent = pp;
            pp->right->parent = nullptr;
        }
        
        pp->right = v;
        v->parent = pp;
        v->pathParent = nullptr;
        pp->pull();
        
        last = pp;
        splay(v);
    }
    
    return last; // Returns root of the represented tree
}

After access(v), the path from v to the root is a single preferred path. Splaying v brings it to the splay tree root. The right subtree (deeper nodes) gets detached since v is now the deepest node on the preferred path.

Primitive Operations: Link and Cut

With access implemented, link and cut become straightforward:

void link(Node* v, Node* w) {
    // Make v the root of its tree, then attach to w
    access(v);
    access(w);
    
    // v should be a tree root (no left child after access + makeRoot)
    v->left = w;
    w->parent = v;
    v->pull();
}

void cut(Node* v) {
    // Separate v from its parent in the represented tree
    access(v);
    
    if (v->left) {
        v->left->parent = nullptr;
        v->left = nullptr;
        v->pull();
    }
}

// Cut the edge between v and w specifically
void cut(Node* v, Node* w) {
    makeRoot(v);  // See next section
    access(w);
    
    if (w->left == v) {
        w->left->parent = nullptr;
        w->left = nullptr;
        w->pull();
    }
}

The link operation requires v to be a root in its represented tree. After accessing both nodes, we simply make w the left child of v (since w is shallower in the new combined tree).

Path Queries and Aggregation

To query arbitrary paths (not just to root), we need makeRoot, which reorients the tree to make any node the root:

void makeRoot(Node* v) {
    access(v);
    v->reversed ^= true;
    v->push();
}

Node* findRoot(Node* v) {
    access(v);
    while (v->left) {
        v->push();
        v = v->left;
    }
    splay(v);
    return v;
}

long long pathQuery(Node* u, Node* v) {
    makeRoot(u);
    access(v);
    return v->pathSum;
}

bool connected(Node* u, Node* v) {
    if (u == v) return true;
    access(u);
    access(v);
    return u->parent != nullptr || u->pathParent != nullptr;
}

The reversal flag lazily flips the tree orientation. When we make v the root, all ancestor-descendant relationships along the path from the old root to v get inverted.

Implementation Considerations

Common bugs that will cost you hours:

Forgetting to push before accessing children: Lazy propagation requires pushing before reading child pointers.
Path-parent vs parent confusion: Only splay tree children have proper parent pointers. Path-parent connections don’t set the parent’s child pointer.
Not pulling after modifications: Every structural change requires updating aggregates up the tree.
isRoot() edge cases: A node is a splay root if it has no parent OR if its parent doesn’t claim it as a child.

For performance, consider node pooling to avoid allocation overhead. The splay tree’s self-adjusting property means recently accessed nodes stay near the root, providing good cache locality for repeated queries on similar paths.

Complexity Analysis and Comparisons

The amortized O(log n) bound comes from splay tree analysis. Each access operation performs O(log n) amortized splay operations, and the total work across all accesses is bounded by the access lemma.

Comparison with alternatives:

Operation	Link-Cut Tree	Heavy-Light Decomposition	Euler Tour Tree
Path query	O(log n)	O(log² n)	O(log n)
Path update	O(log n)	O(log² n)	O(log n)
Link	O(log n)	O(n)	O(log n)
Cut	O(log n)	O(n)	O(log n)
Subtree query	O(n)	O(log n)	O(log n)

Choose Link-Cut Trees when you need dynamic connectivity with path queries. Use HLD for static trees with simpler implementation. Euler Tour Trees excel at subtree operations but can’t easily support path queries.

Link-Cut Trees are the right tool when your tree structure changes and you need path operations. The implementation complexity is real—expect to spend time debugging—but the algorithmic power is unmatched for dynamic tree problems.