Link-Cut Trees (LCT): Key Operations and Applications for Dynamic Forests

Link-Cut Trees are a dynamic tree data structure that maintains a forest of rooted trees and supports link, cut, and path aggregation operations in amortized O(log N) time per operation using splay-tree-based preferred paths.

Link-Cut Trees (LCT) represent one of the most powerful tools in competitive programming and advanced algorithm design for handling dynamic trees—forest structures that change over time through edge insertions and deletions. The hzwer/shareoi repository contains theoretical presentations on this topic, including detailed discussions of dynamic sequence structures in 数据结构/动态序列与动态树问题——浅谈几种常用数据结构_莫凡.pdf. This article explores the fundamental operations, amortized complexity guarantees, and practical implementations of Link-Cut Trees based on the algorithmic theory covered in the repository.

Core Concepts and Architecture

Link-Cut Trees solve the dynamic connectivity problem by representing each tree as a collection of preferred paths—maximal chains of preferred edges from each node toward the root. The data structure maintains these paths as auxiliary splay trees, allowing local restructuring that adapts to access patterns.

Each node stores a path-parent pointer (the topmost node’s connection to the next preferred path) and standard splay tree pointers. The amortized O(log N) bound emerges because each access operation manipulates only a constant number of splay trees, and splay trees provide the required amortized logarithmic performance for restructuring.

Fundamental Link-Cut Tree Operations

The LCT interface exposes several primitive operations that enable dynamic forest manipulation:

• access(u) — Creates a preferred path from the root of the tree to node u, making u the rightmost node in its auxiliary splay tree. This is the fundamental primitive upon which all other operations build.
• evert(u) — Reorients the tree to make u the new root. Implemented by calling access(u) followed by toggling a lazy reversal flag on the splay tree node.
• link(u, v) — Connects two trees by making root u a child of node v. Requires calling evert(u) first to ensure u is a root, then setting its path-parent to v.
• cut(u, v) — Removes the edge between u and v (typically between u and its parent). Implemented by calling evert(u) followed by access(v), which isolates the edge as the left child relationship in the splay tree.

Path Queries and Dynamic Updates

Beyond topology changes, Link-Cut Trees excel at path aggregation—computing associative functions (sum, minimum, maximum, XOR) over the unique path between any two nodes.

To query the path from u to v, the implementation calls evert(u) to make u the root, then access(v) to expose the path as a single splay tree rooted at v. The aggregate value stored at v (typically maintained in a sum or mx field) then represents the answer for the entire u-v path.

Point updates modify node values in O(log N) time by calling access(u) to bring the node to the top of its auxiliary tree, updating its stored value, and invoking pull() to propagate the change upward through the splay tree ancestors.

Real-World Applications of Dynamic Trees

Link-Cut Trees enable solutions to problems that static tree decompositions cannot handle:

• Dynamic Connectivity — Maintaining a forest while edges are added and removed, with the ability to test if two vertices belong to the same component via connected(u, v) checks (comparing findRoot results).
• Network Flow on Mutable Graphs — Updating edge capacities dynamically and recomputing min-cut or max-flow without rebuilding the entire flow network from scratch.
• Tree-Path Competition Problems — Solving classic OI/ICPC tasks such as "Maximum edge weight on a path," "Path sum with point updates," and "Kth ancestor after edge deletions."
• Heavy-Light Decomposition Replacement — Providing a fully dynamic alternative to static HLD when the problem requires both path queries and link/cut operations.
• Dynamic Minimum Spanning Trees — Maintaining the minimum spanning forest under edge insertions and deletions using approaches like Dynamic Kruskal.

C++17 Implementation of Link-Cut Trees

Below is a complete, self-contained implementation supporting path sum queries, dynamic node updates, and forest manipulation. The code uses the splay tree mechanism described in 数据结构/动态序列与动态树问题——浅谈几种常用数据结构_莫凡.pdf within the hzwer/shareoi repository.

// Link‑Cut Tree (path aggregate – sum) – C++17
// Source: adapted from classic LCT literature
struct LinkCut {
    struct Node {
        Node *ch[2]{}, *fa{};
        bool rev = false;          // lazy reversal flag
        long long val = 0, sum = 0; // vertex value and subtree sum
        // update aggregate from children
        void pull() { sum = val; if (ch[0]) sum += ch[0]->sum; if (ch[1]) sum += ch[1]->sum; }
        // propagate lazy reversal
        void push() {
            if (!rev) return;
            swap(ch[0], ch[1]);
            if (ch[0]) ch[0]->rev ^= 1;
            if (ch[1]) ch[1]->rev ^= 1;
            rev = false;
        }
        bool isRoot() const {
            return !fa || (fa->ch[0] != this && fa->ch[1] != this);
        }
    };

    vector<Node> pool;
    LinkCut(int n = 0) : pool(n + 1) {}

    // rotate x up
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int dx = (y->ch[1] == x);
        int dy = (z && z->ch[1] == y);
        Node *b = x->ch[dx ^ 1];
        if (!y->isRoot()) z->ch[dy] = x;
        x->fa = z;
        x->ch[dx ^ 1] = y; y->fa = x;
        y->ch[dx] = b; if (b) b->fa = y;
        y->pull(); x->pull();
    }

    // splay x to the root of its auxiliary tree
    void splay(Node *x) {
        static vector<Node*> stk;
        stk.clear();
        for (Node *y = x; ; y = y->fa) {
            stk.push_back(y);
            if (y->isRoot()) break;
        }
        while (!stk.empty()) { stk.back()->push(); stk.pop_back(); }

        while (!x->isRoot()) {
            Node *y = x->fa;
            if (!y->isRoot()) rotate((y->ch[0] == x) ^ (y->fa->ch[0] == y) ? x : y);
            rotate(x);
        }
    }

    // expose path from root to x, making x the rightmost node in its aux tree
    Node* access(Node *x) {
        Node *last = nullptr;
        for (Node *y = x; y; y = y->fa) {
            splay(y);
            y->ch[1] = last;
            y->pull();
            last = y;
        }
        splay(x);
        return last;
    }

    // make x the root of its represented tree
    void evert(Node *x) {
        access(x);
        x->rev ^= 1;
    }

    // link u as a child of v (u must be a root)
    bool link(int u, int v) {
        Node *a = &pool[u], *b = &pool[v];
        evert(a);
        if (findRoot(b) == a) return false; // already connected
        a->fa = b;
        return true;
    }

    // cut edge between u and its parent
    bool cut(int u, int v) {
        Node *a = &pool[u], *b = &pool[v];
        evert(a);
        access(b);
        // after evert+access, a is left child of b if edge exists
        if (b->ch[0] != a || a->ch[1]) return false;
        b->ch[0] = a->fa = nullptr;
        b->pull();
        return true;
    }

    // find root of the tree containing x
    Node* findRoot(Node *x) {
        access(x);
        while (x->push(), x->ch[0]) x = x->ch[0];
        splay(x);
        return x;
    }

    // path sum query u‑v
    long long pathSum(int u, int v) {
        Node *a = &pool[u], *b = &pool[v];
        evert(a);
        access(b);
        return b->sum;
    }

    // point update
    void setVal(int u, long long val) {
        Node *x = &pool[u];
        access(x);
        x->val = val;
        x->pull();
    }

    // convenience wrappers
    bool connected(int u, int v) { return findRoot(&pool[u]) == findRoot(&pool[v]); }
    Node* node(int id) { return &pool[id]; }
};

Usage Example:

int main() {
    const int N = 5;
    LinkCut lct(N);
    // initialise vertex values
    for (int i = 1; i <= N; ++i) lct.setVal(i, i);  // val = index

    // Build a tree: 1‑2‑3, 4‑5
    lct.link(2, 1);
    lct.link(3, 2);
    lct.link(5, 4);

    // Path sum 3 → 1 (should be 1+2+3 = 6)
    cout << lct.pathSum(3, 1) << '\n';

    // Change weight of vertex 2
    lct.setVal(2, 10);
    cout << lct.pathSum(3, 1) << '\n'; // now 1+10+3 = 14

    // Cut edge (2,1) and link 2 under 4
    lct.cut(2, 1);
    lct.link(2, 4);

    // Are 1 and 5 connected now? → false
    cout << lct.connected(1,5) << '\n';
}

Algorithm Theory Resources in hzwer/shareoi

While the hzwer/shareoi repository focuses on algorithmic theory presentations rather than reference implementations, the following files provide essential background on dynamic trees and related static alternatives:

• 数据结构/动态序列与动态树问题——浅谈几种常用数据结构_莫凡.pdf — Discusses dynamic sequence structures including Link-Cut Trees and their theoretical foundations.
• 数据结构/树链剖分_王天懿.ppt — Presentation on Heavy-Light Decomposition, the static counterpart to LCT for problems without dynamic link/cut requirements.
• 图论/树链剖分及其应用_蒋一瑶.pptx — Extended examples of path queries on trees using HLD, useful for understanding the query semantics before adding dynamic operations.
• README.md — General overview of the repository’s algorithmic topics and presentation structure.

Summary

• Link-Cut Trees maintain a dynamic forest using splay-tree-based preferred paths, achieving amortized O(log N) per operation.
• Core operations include evert (re-rooting), link (connecting trees), cut (removing edges), and access (path exposure).
• Path aggregates (sum, min, max) are computed by re-rooting one endpoint and exposing the path to the other, storing results in splay tree nodes.
• The data structure solves dynamic connectivity, mutable network flows, and dynamic MST problems that static decompositions cannot handle.
• The hzwer/shareoi repository provides theoretical context in 数据结构/动态序列与动态树问题——浅谈几种常用数据结构_莫凡.pdf, while competitive programming implementations require standalone C++ code like the example above.

Frequently Asked Questions

What is the time complexity of Link-Cut Tree operations?

All standard Link-Cut Tree operations—including link, cut, evert, and path queries—run in amortized O(log N) time per operation. This bound holds because each operation manipulates only a constant number of splay trees, and splay trees provide logarithmic amortized performance for restructuring sequences of accesses.

How do Link-Cut Trees differ from Heavy-Light Decomposition?

Heavy-Light Decomposition (HLD) is a static technique that decomposes a tree into heavy and light chains to answer path queries in O(log² N) or O(log N) time, but it cannot efficiently handle dynamic edge insertions or deletions. Link-Cut Trees provide a fully dynamic alternative that supports both path queries and forest modifications (link/cut) in amortized O(log N) time, making them suitable for problems where the tree topology changes during execution.

Can Link-Cut Trees handle subtree queries or only path queries?

Standard Link-Cut Trees are optimized for path queries between two nodes. However, they can be extended to support subtree queries by maintaining virtual child sizes within each splay node or by using auxiliary data structures. For pure subtree aggregates without path requirements, other dynamic tree structures like Euler Tour Trees often provide simpler implementations, though LCT extensions exist for competitive programming scenarios requiring both capabilities.

Why is the access operation considered the fundamental primitive in LCT?

The access(u) operation creates a preferred path from the tree root to node u, making u the rightmost node in its auxiliary splay tree while breaking previous preferred paths above it. This primitive enables every other operation: evert calls access followed by a reversal flag, pathSum uses access to expose the path between endpoints, and link/cut rely on access to establish or sever parent-child relationships in the represented forest. Without access, the preferred path invariant that maintains the amortized complexity guarantees cannot be enforced.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}