🗂️Data StructureAdvanced

Link-Cut Tree

Key Points

  • •
    A Link-Cut Tree (LCT) maintains a dynamic forest and supports link, cut, and path queries in O(log n) amortized time.
  • •
    It decomposes each tree into preferred paths and stores each preferred path as a splay tree (an auxiliary tree).
  • •
    The core operation is access, which exposes the root-to-node path and makes it the current preferred path.
  • •
    LCTs are ideal for dynamic connectivity, dynamic Lowest Common Ancestor (LCA), and path aggregates in changing trees.
  • •
    Path queries and updates reduce to splaying a node that represents the entire path as one splay tree and reading or updating its aggregate.
  • •
    Makeroot lets you treat any node as the root of its represented tree, enabling symmetric path operations.
  • •
    Amortized guarantees come from splay tree potential analysis, yielding O(log n) per operation on average over sequences.
  • •
    LCTs handle path queries well but do not directly support subtree queries (use Euler Tour Trees for subtree aggregates).

Prerequisites

  • →Binary Trees and Rotations — Splay trees inside LCT rely on rotations (zig, zig-zig, zig-zag) to restructure trees.
  • →Splay Trees — Auxiliary trees are splay trees; understanding splaying and amortized analysis is essential.
  • →Tree Data Structures — Familiarity with rooted trees, paths, and LCA helps reason about represented forests.
  • →Amortized Analysis — LCT performance guarantees hinge on amortized O(log n) bounds from splay trees.
  • →Lazy Propagation — Path updates (like add or reverse) are implemented via lazy tags in splay nodes.
  • →Heavy-Light Decomposition (HLD) — Helpful comparison to understand when to prefer LCT vs static-tree techniques.

Detailed Explanation

Tap terms for definitions

01Overview

A Link-Cut Tree (LCT) is a powerful data structure for maintaining a dynamic forest of rooted or unrooted trees under edge insertions and deletions while supporting fast path queries. It gives amortized O(log n) time for operations like link(u, v) to add an edge between roots, cut(u, v) to remove an existing edge, connected(u, v) to test whether two nodes are in the same tree, and path aggregates such as sum, min, or xor along the unique path between two nodes. The LCT achieves this by decomposing each represented tree into preferred paths. Each preferred path is maintained as a balanced binary search tree—specifically, a splay tree—called an auxiliary tree. The key primitive access(u) rearranges the preferred paths so that the path from the represented root to u becomes preferred and ends up as the right spine of a splayed auxiliary tree. This manipulation allows path queries or updates to be localized to a single splay tree, enabling efficient updates and queries. Link-Cut Trees are widely used in competitive programming and dynamic graph problems where the underlying graph is always a forest, but edges change over time.

02Intuition & Analogies

Imagine a city’s road network where each neighborhood (node) is connected by streets forming no cycles (a forest). You frequently need to do two tasks: sometimes you open or close a street (link/cut), and other times you want to get information about all neighborhoods along a specific route (a path query/update). Instead of scanning the whole route every time, you choose certain streets as “express lanes” to speed up future trips—these are the preferred edges. Whenever your focus shifts to a different route, you realign which streets are express. The access operation is like repainting the express lanes to follow the current root-to-target route. Now, if you want to gather tolls or set a new toll on all neighborhoods along a route, the express lane structure lines them up in one place so that a single pass can handle the entire route efficiently. The express lanes are stored in small, flexible substructures (splay trees) that are easy to rearrange on the fly. Splay trees have the neat property that restructuring them according to recent access patterns keeps operations fast on average. Makeroot is like deciding where the city’s zero-mile marker is; by changing the viewpoint, you can make any route a root-to-leaf route and then apply the same efficient strategy. Even though the road painting (access) might seem costly in the moment, the average cost is low thanks to how often you reuse the structure.

03Formal Definition

A Link-Cut Tree maintains a forest F of rooted trees (represented trees). Each represented tree is decomposed into preferred paths based on the most recently accessed nodes. A preferred path is a maximal path following child pointers marked as preferred (solid edges), while other edges are light. Each preferred path is stored as an auxiliary splay tree whose in-order traversal corresponds to the path order. Each node x belongs to exactly one auxiliary tree at any time. The central primitive is access(x): it transforms the preferred path decomposition so that the path from the root of x’s represented tree to x is a single preferred path. After access(x), x is splayed to the root of its auxiliary tree, and its right child represents the portion of the path strictly below x that is not preferred. The operations are defined as follows: makeroot(x) = access(x) followed by reversing x’s auxiliary tree so x becomes the represented root; findroot(x) = after access(x), traverse left children with pushes to find the minimum in the auxiliary tree; split(u, v) = makeroot(u), access(v), producing an auxiliary tree at v that represents the unique path link(u, v) connects two represented roots, and cut(u, v) removes the represented edge between u and v. Aggregates over a path become aggregates over the splayed auxiliary tree at v after split(u, v). Amortized O(log n) bounds follow from splay tree potential analysis applied to auxiliary trees.

04When to Use

Use Link-Cut Trees when you need fast updates and queries on changing trees (forests). Typical scenarios include: dynamic connectivity in forests (adding/removing edges with connectivity checks), dynamic LCA queries as edges or roots change, and path aggregates like sum, min, max, xor, or even lazy range updates (path add/assign) when you can maintain them in splay nodes. They excel when queries are about paths between arbitrary nodes rather than about entire subtrees. They are particularly effective in competitive programming tasks where the underlying structure is guaranteed to be a forest at all times. You should prefer LCTs over static tree techniques (like Heavy-Light Decomposition) when the topology changes frequently (link/cut). If you only need static-tree path queries with many updates to edge/node values but no topology changes, Heavy-Light Decomposition is simpler. If your queries are subtree-based (sum over all descendants) under dynamic edges, Euler Tour Trees (ETT) may be more natural than LCT, because LCT focuses on root-to-node paths via preferred path decompositions. For dense graphs with cycles, LCT is not appropriate unless you restrict operations to maintain a forest.

⚠️Common Mistakes

Common pitfalls include: (1) Forgetting to propagate lazy flags (reverse or add/assign) before rotations or traversals. Always push down from ancestors to the node being splayed to keep auxiliary trees correct. (2) Incorrect isRoot checks for splay trees: a node is a splay root if it is not a child of its parent via ch[0] or ch[1]. Mixing represented-tree roots with splay roots is a frequent confusion. (3) Linking two nodes already connected, which would create a cycle and violate the forest invariant. Always check connected(u, v) before link(u, v). (4) Using path aggregates that are not properly maintained by in-order combination of left, self, right, or forgetting to update size/sum during pushup. (5) Mixing up makeroot and split orders; to get the path between u and v, you must makeroot(u) then access(v). (6) Implementing cut(u, v) incorrectly—after makeroot(u) and access(v), you must verify that v’s left child is u and that u has no right child before severing. (7) Assuming LCT supports subtree queries directly; it does not, unless you remodel the problem (e.g., virtual tree tricks or use Euler Tour Trees). (8) Writing recursive splay without guarding stack depth or missing the top-down push sequence, leading to bugs and timeouts.

Key Formulas

Amortized Time per Operation

Explanation: Each link, cut, access, and path query runs in amortized logarithmic time in the number of nodes. While a single operation might take longer, the average over many operations is bounded by a logarithmic function.

Splay Tree Potential Function

Explanation: A common potential function for splay trees sums the logarithms of subtree sizes. Changes in this potential bound the amortized cost of splay operations.

Total Cost Over m Operations

Explanation: Executing m LCT operations on a forest of n nodes costs proportional to m times log n in the amortized sense. This is the key performance guarantee in practice.

Rotation Cost Bound Pattern

Explanation: This classic sum appears in bounding worst-case sequences of rotations, but amortized analysis via potential ensures the average per operation is logarithmic rather than linear.

Path Sum

Explanation: The sum over node weights along path P(u, v). In an LCT, after split(u, v), this is available as the aggregate value at the root of the auxiliary tree.

Path Add Update

Explanation: Adding to every node on the path increases the path sum by times the number of nodes on the path. LCT uses a lazy add tag and node sizes to implement this in O(1) at the splay root.

Complexity Analysis

Link-Cut Trees achieve amortized O(log n) time per operation by representing preferred paths as splay trees and using access to expose a desired path. Each access(x) walks upward through at most O(log n) preferred path boundaries in an amortized sense, performing a constant number of splay operations per boundary. The splay operation itself has amortized O(log n) complexity under the classic potential method, where the potential is the sum over nodes of log of auxiliary-subtree sizes. Therefore, the total amortized cost of access is O(log n). Operations link(u, v) and cut(u, v) perform a constant number of access and splay calls, so they are amortized O(log n). Path queries and updates, such as sum on path or add on path, reduce to split(u, v) = makeroot(u) followed by access(v), which is again O(log n) amortized. Maintaining aggregates and lazy tags (like reverse or add) only requires O(1) additional work per rotation and push, preserving the asymptotic bounds. Space usage is O(n), storing per-node parent pointers, two child pointers, flags (rev, lazy tags), and aggregate fields (value, size, sum). There is no extra per-edge structure unless modeling edge weights via edge-nodes. Compared to alternatives, Heavy-Light Decomposition also provides O(log n) for static topology but struggles with edge deletions, while Euler Tour Trees handle connectivity and subtree queries but are less natural for path aggregates with complex lazy updates. LCT’s strength lies in general path operations under dynamic topologies with predictable amortized logarithmic performance.

Code Examples

Full Link-Cut Tree with Path Sum and Path Add (Node Weights)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct LCT {
5    struct Node {
6        int ch[2] = {0, 0};
7        int fa = 0;           // parent in auxiliary (splay) tree
8        bool rev = false;     // reverse flag for path reversal
9        long long val = 0;    // value stored at this node (node weight)
10        long long sum = 0;    // aggregate sum over the splay subtree
11        long long add = 0;    // lazy add tag applied to entire splay subtree
12        int siz = 1;          // number of nodes in splay subtree
13    };
14
15    int n;
16    vector<Node> t;
17
18    LCT(int n = 0) { init(n); }
19
20    void init(int n_) {
21        n = n_;
22        t.assign(n + 1, Node());
23        for (int i = 1; i <= n; ++i) t[i].siz = 1;
24    }
25
26    // Utility: is x a root of its auxiliary (splay) tree?
27    bool isRoot(int x) {
28        int f = t[x].fa;
29        return f == 0 || (t[f].ch[0] != x && t[f].ch[1] != x);
30    }
31
32    void pushRev(int x) {
33        if (!x) return;
34        swap(t[x].ch[0], t[x].ch[1]);
35        t[x].rev ^= 1;
36    }
37
38    void pushAdd(int x, long long v) {
39        if (!x) return;
40        t[x].val += v;
41        t[x].sum += v * t[x].siz;
42        t[x].add += v;
43    }
44
45    void pushUp(int x) {
46        t[x].siz = 1;
47        t[x].sum = t[x].val;
48        if (t[x].ch[0]) {
49            t[x].siz += t[t[x].ch[0]].siz;
50            t[x].sum += t[t[x].ch[0]].sum;
51        }
52        if (t[x].ch[1]) {
53            t[x].siz += t[t[x].ch[1]].siz;
54            t[x].sum += t[t[x].ch[1]].sum;
55        }
56    }
57
58    void pushDown(int x) {
59        if (t[x].rev) {
60            if (t[x].ch[0]) pushRev(t[x].ch[0]);
61            if (t[x].ch[1]) pushRev(t[x].ch[1]);
62            t[x].rev = false;
63        }
64        if (t[x].add) {
65            if (t[x].ch[0]) pushAdd(t[x].ch[0], t[x].add);
66            if (t[x].ch[1]) pushAdd(t[x].ch[1], t[x].add);
67            t[x].add = 0;
68        }
69    }
70
71    void rotate(int x) {
72        int y = t[x].fa, z = t[y].fa;
73        int dx = (t[y].ch[1] == x);
74        int b = t[x].ch[dx ^ 1];
75        if (!isRoot(y)) {
76            if (t[z].ch[0] == y) t[z].ch[0] = x;
77            else if (t[z].ch[1] == y) t[z].ch[1] = x;
78        }
79        t[x].fa = z;
80        t[x].ch[dx ^ 1] = y; t[y].fa = x;
81        t[y].ch[dx] = b; if (b) t[b].fa = y;
82        pushUp(y); pushUp(x);
83    }
84
85    void pushAll(int x) {
86        static vector<int> st; st.clear();
87        int u = x; st.push_back(u);
88        while (!isRoot(u)) { u = t[u].fa; st.push_back(u); }
89        for (int i = (int)st.size() - 1; i >= 0; --i) pushDown(st[i]);
90    }
91
92    void splay(int x) {
93        pushAll(x);
94        while (!isRoot(x)) {
95            int y = t[x].fa, z = t[y].fa;
96            if (!isRoot(y)) {
97                bool zigzig = (t[y].ch[0] == x) == (t[z].ch[0] == y);
98                if (zigzig) rotate(y); else rotate(x);
99            }
100            rotate(x);
101        }
102        pushUp(x);
103    }
104
105    // Expose root-to-x path; after this, x is root of its aux tree, and right child is null.
106    void access(int x) {
107        int last = 0;
108        for (int u = x; u; u = t[u].fa) {
109            splay(u);
110            t[u].ch[1] = last;
111            pushUp(u);
112            last = u;
113        }
114        splay(x);
115    }
116
117    // Make x the root of its represented tree
118    void makeroot(int x) {
119        access(x);
120        pushRev(x);
121    }
122
123    // Find represented root of x
124    int findroot(int x) {
125        access(x);
126        int u = x;
127        while (true) {
128            pushDown(u);
129            if (!t[u].ch[0]) break;
130            u = t[u].ch[0];
131        }
132        splay(u);
133        return u;
134    }
135
136    // Make path u-v the aux tree at v
137    void split(int u, int v) {
138        makeroot(u);
139        access(v); // now v's splay covers path u..v
140    }
141
142    bool connected(int u, int v) {
143        return findroot(u) == findroot(v);
144    }
145
146    bool link(int u, int v) {
147        makeroot(u);
148        if (findroot(v) == u) return false; // already connected -> would form a cycle
149        t[u].fa = v;
150        return true;
151    }
152
153    bool cut(int u, int v) {
154        makeroot(u);
155        access(v);
156        // Now, u should be v's left child and have no right child
157        if (t[v].ch[0] != u || t[u].ch[1] != 0) return false;
158        t[v].ch[0] = 0; t[u].fa = 0; pushUp(v);
159        return true;
160    }
161
162    // Set initial node value
163    void set_val(int x, long long w) {
164        access(x);
165        t[x].val = w;
166        pushUp(x);
167    }
168
169    // Add delta to all nodes on path u..v
170    void path_add(int u, int v, long long delta) {
171        split(u, v);
172        pushAdd(v, delta);
173    }
174
175    // Sum of values on path u..v
176    long long path_sum(int u, int v) {
177        split(u, v);
178        return t[v].sum;
179    }
180};
181
182int main() {
183    ios::sync_with_stdio(false);
184    cin.tie(nullptr);
185
186    int n = 6;
187    LCT lct(n);
188    for (int i = 1; i <= n; ++i) lct.set_val(i, i); // values = 1..n
189
190    // Build a path 1-2-3 and 4-5-6
191    lct.link(1, 2);
192    lct.link(2, 3);
193    lct.link(4, 5);
194    lct.link(5, 6);
195
196    cout << (lct.connected(1, 3) ? "YES" : "NO") << "\n"; // YES
197    cout << (lct.connected(1, 5) ? "YES" : "NO") << "\n"; // NO
198
199    // Path sum 1..3: 1+2+3 = 6
200    cout << lct.path_sum(1, 3) << "\n";
201
202    // Add 10 to nodes on path 2..3: nodes {2,3}
203    lct.path_add(2, 3, 10);
204    cout << lct.path_sum(1, 3) << "\n"; // 1 + (2+10) + (3+10) = 26
205
206    // Connect the two components via 3-4
207    lct.link(3, 4);
208    cout << (lct.connected(1, 6) ? "YES" : "NO") << "\n"; // YES
209
210    // Cut edge 2-3
211    lct.cut(2, 3);
212    cout << (lct.connected(1, 6) ? "YES" : "NO") << "\n"; // NO
213
214    return 0;
215}
216

This is a full-featured Link-Cut Tree supporting link, cut, connectivity, path sum, and path add on node weights. Preferred paths are stored as splay trees; access exposes a root-to-node path. split(u, v) makes the path u..v correspond to a single auxiliary tree rooted at v, so we can read/update its aggregate in O(1) at the splay root with lazy tags. The main demonstrates connectivity, path sum, path add, link, and cut.

Time: O(log n) amortized per operationSpace: O(n)
Dynamic LCA with Link-Cut Tree
1#include <bits/stdc++.h>
2using namespace std;
3
4struct LCT {
5    struct Node { int ch[2]={0,0}; int fa=0; bool rev=false; int siz=1; };
6    int n; vector<Node> t;
7    LCT(int n=0){init(n);} void init(int n_){n=n_; t.assign(n+1, Node()); for(int i=1;i<=n;++i) t[i].siz=1;}
8    bool isRoot(int x){int f=t[x].fa; return f==0 || (t[f].ch[0]!=x && t[f].ch[1]!=x);} 
9    void pushRev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev^=1; }
10    void pushDown(int x){ if(t[x].rev){ if(t[x].ch[0]) pushRev(t[x].ch[0]); if(t[x].ch[1]) pushRev(t[x].ch[1]); t[x].rev=false; } }
11    void pushUp(int x){ t[x].siz = 1; if(t[x].ch[0]) t[x].siz += t[t[x].ch[0]].siz; if(t[x].ch[1]) t[x].siz += t[t[x].ch[1]].siz; }
12    void rotate(int x){int y=t[x].fa,z=t[y].fa; int dx=(t[y].ch[1]==x); int b=t[x].ch[dx^1]; if(!isRoot(y)){ if(t[z].ch[0]==y) t[z].ch[0]=x; else if(t[z].ch[1]==y) t[z].ch[1]=x; } t[x].fa=z; t[x].ch[dx^1]=y; t[y].fa=x; t[y].ch[dx]=b; if(b) t[b].fa=y; pushUp(y); pushUp(x);} 
13    void pushAll(int x){ static vector<int> st; st.clear(); int u=x; st.push_back(u); while(!isRoot(u)){ u=t[u].fa; st.push_back(u);} for(int i=(int)st.size()-1;i>=0;--i) pushDown(st[i]); }
14    void splay(int x){ pushAll(x); while(!isRoot(x)){ int y=t[x].fa, z=t[y].fa; if(!isRoot(y)){ bool zz=(t[y].ch[0]==x)==(t[z].ch[0]==y); if(zz) rotate(y); else rotate(x);} rotate(x);} pushUp(x);} 
15    void access(int x){ int last=0; for(int u=x; u; u=t[u].fa){ splay(u); t[u].ch[1]=last; pushUp(u); last=u; } splay(x);} 
16    void makeroot(int x){ access(x); pushRev(x);} 
17    int findroot(int x){ access(x); int u=x; while(true){ pushDown(u); if(!t[u].ch[0]) break; u=t[u].ch[0]; } splay(u); return u; }
18    bool link(int u,int v){ makeroot(u); if(findroot(v)==u) return false; t[u].fa=v; return true; }
19    bool cut(int u,int v){ makeroot(u); access(v); if(t[v].ch[0]!=u || t[u].ch[1]) return false; t[v].ch[0]=0; t[u].fa=0; pushUp(v); return true; }
20    // LCA: after access(u), the last node whose fa becomes 0 during access(v) is the LCA.
21    int lca(int u, int v){ if(findroot(u)!=findroot(v)) return 0; access(u); int res=0; for(int x=v; x; x=t[x].fa){ splay(x); if(t[x].fa==0) res=x; t[x].ch[1]=0; pushUp(x); } access(v); return res; }
22};
23
24int main(){
25    ios::sync_with_stdio(false);
26    cin.tie(nullptr);
27
28    int n=7; LCT lct(n);
29    // Build tree: 1-2-3-4 and 2-5, 5-6, 6-7 (a chain with a branch via link operations)
30    lct.link(1,2); lct.link(2,3); lct.link(3,4); lct.link(2,5); lct.link(5,6); lct.link(6,7);
31
32    cout << lct.lca(4,7) << "\n"; // Expected 2
33    cout << lct.lca(3,5) << "\n"; // Expected 2
34
35    // Cut 2-5 breaks the branch
36    lct.cut(2,5);
37    cout << lct.lca(4,7) << "\n"; // Now disconnected, returns 0
38    return 0;
39}
40

This example shows how to compute LCA dynamically with an LCT. The lca(u, v) method uses the property that after access(u), performing access(v) yields the LCA as the highest node whose parent becomes null during the procedure. It gracefully adapts to edge insertions and deletions.

Time: O(log n) amortized per LCASpace: O(n)
Dynamic Connectivity in a Forest (link, cut, connected)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct LCT {
5    struct Node { int ch[2]={0,0}; int fa=0; bool rev=false; };
6    int n; vector<Node> t;
7    LCT(int n=0){init(n);} void init(int n_){n=n_; t.assign(n+1, Node());}
8    bool isRoot(int x){int f=t[x].fa; return f==0 || (t[f].ch[0]!=x && t[f].ch[1]!=x);} 
9    void pushRev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev^=1; }
10    void pushDown(int x){ if(t[x].rev){ if(t[x].ch[0]) pushRev(t[x].ch[0]); if(t[x].ch[1]) pushRev(t[x].ch[1]); t[x].rev=false; } }
11    void rotate(int x){int y=t[x].fa,z=t[y].fa; int dx=(t[y].ch[1]==x); int b=t[x].ch[dx^1]; if(!isRoot(y)){ if(t[z].ch[0]==y) t[z].ch[0]=x; else if(t[z].ch[1]==y) t[z].ch[1]=x; } t[x].fa=z; t[x].ch[dx^1]=y; t[y].fa=x; t[y].ch[dx]=b; if(b) t[b].fa=y; }
12    void pushAll(int x){ static vector<int> st; st.clear(); int u=x; st.push_back(u); while(!isRoot(u)){ u=t[u].fa; st.push_back(u);} for(int i=(int)st.size()-1;i>=0;--i) pushDown(st[i]); }
13    void splay(int x){ pushAll(x); while(!isRoot(x)){ int y=t[x].fa, z=t[y].fa; if(!isRoot(y)){ bool zz=(t[y].ch[0]==x)==(t[z].ch[0]==y); if(zz) rotate(y); else rotate(x);} rotate(x);} }
14    void access(int x){ int last=0; for(int u=x; u; u=t[u].fa){ splay(u); t[u].ch[1]=last; last=u; } splay(x);} 
15    void makeroot(int x){ access(x); pushRev(x);} 
16    int findroot(int x){ access(x); int u=x; while(true){ pushDown(u); if(!t[u].ch[0]) break; u=t[u].ch[0]; } splay(u); return u; }
17    bool connected(int u,int v){ return findroot(u)==findroot(v); }
18    bool link(int u,int v){ makeroot(u); if(findroot(v)==u) return false; t[u].fa=v; return true; }
19    bool cut(int u,int v){ makeroot(u); access(v); if(t[v].ch[0]!=u || t[u].ch[1]) return false; t[v].ch[0]=0; t[u].fa=0; return true; }
20};
21
22int main(){
23    ios::sync_with_stdio(false);
24    cin.tie(nullptr);
25
26    int n, q; cin >> n >> q; // nodes are 1..n
27    LCT lct(n);
28    while(q--){
29        string op; int u, v; cin >> op >> u >> v;
30        if(op=="link"){ if(!lct.link(u,v)) cout << "error\n"; }
31        else if(op=="cut"){ if(!lct.cut(u,v)) cout << "error\n"; }
32        else if(op=="connected"){ cout << (lct.connected(u,v)?"YES":"NO") << '\n'; }
33    }
34    return 0;
35}
36

This is a minimal LCT tailored to dynamic connectivity. It supports link, cut, and connected in amortized O(log n). The input format makes it easy to test sequences of operations online.

Time: O(log n) amortized per operationSpace: O(n)