Link-Cut Tree
A dynamic-forest structure built on splay trees for link, cut, reroot, and path-query operations.
Link-Cut Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Link-cut trees maintain a dynamic forest under rerooting, linking, cutting, and path queries. They are one of the few structures in contest programming that really feel layered: the public API talks about trees, but the implementation is powered by splay trees over preferred paths.
This is an advanced note because both the idea and the debugging burden are real. Still, once the structure clicks, it becomes one of the cleanest ways to handle dynamic-tree path queries in \(O(\log n)\) amortized time.
When to Use It
Use a link-cut tree when:
the forest changes over time,
queries are about paths rather than static subtrees,
you need operations like
link,cut,make_root, or path aggregate queries,heavy-light decomposition is not enough because the represented tree itself is dynamic.
If the tree is static, heavy-light decomposition is usually much easier to trust and implement.
Core Idea
The represented forest is decomposed into preferred paths. Each preferred path is stored as one auxiliary splay tree.
The central operation is access(x). It repeatedly walks toward the represented root and rewires preferred paths so that the final preferred path from the represented root to \(x\) becomes explicit.
After that exposure, path operations become splay-tree operations on one auxiliary tree.
Key Insight
The phrase that made link-cut trees readable to me is: a link-cut tree is a splay tree data structure for root-to-node exposure.
Everything revolves around exposing a path:
access(x)makes the root-to-\(x\) path preferred,make_root(x)is basically expose + reverse,path queries between \(u\) and \(v\) become ``reroot \(u\), then expose \(v\)''.
So the structure is not maintaining all simple paths directly. It keeps changing which paths are represented explicitly, depending on what was accessed last.
Operations / Main Technique
The standard operations are:
access(x): expose the represented root-to-\(x\) path,
make_root(x): reroot the represented tree at \(x\),
find_root(x): find the represented root of \(x\)'s tree,
link(x, y): connect two different trees,
cut(x, y): remove one represented edge,
connected(x, y): test whether two vertices lie in the same tree,
path_query(x, y): query an aggregate on the path.
Worked path query.
To query the path from \(u\) to \(v\):
call \(\texttt{make\_root(u)}\),
call \(\texttt{access(v)}\),
splay \(v\),
now the auxiliary splay rooted at \(v\) represents exactly the path from \(u\) to \(v\).
So if each splay node stores a path aggregate, the answer is sitting at that auxiliary root.
Correctness Intuition
The auxiliary splay trees are not arbitrary partitions of the represented tree. Each auxiliary tree corresponds to one preferred path, and access is the operation that changes which child edge is preferred at each step upward.
After \(\texttt{make\_root(u)}\), vertex \(u\) becomes the represented root. Then \(\texttt{access(v)}\) exposes the entire path from \(u\) to \(v\) as one preferred path. Since the path is now explicit inside a single auxiliary splay tree, any maintained path aggregate is correct after the usual splay push/pull routines.
Complexity Analysis
access,make_root,link,cut, path queries: \(O(\log n)\) amortized,memory: \(O(n)\).
The amortization comes from the splay-tree layer. Link-cut trees inherit both the power and the caveats of splaying.
Implementation
The reference code keeps a deliberately limited but useful version:
vertex values,
path sums,
link, cut, connected, reroot, and point update.
It does not attempt subtree aggregates or heavy lazy propagation. Those are possible, but they add a second layer of difficulty and deserve their own careful pass.
Common Pitfalls
Building on top of a splay implementation that is not fully reliable.
Forgetting to push the reversal flag before rotations or before walking down the tree.
Confusing the represented-tree parent with the auxiliary-tree parent.
Forgetting that
accesschanges preferred paths globally, not just locally at one node.Trying to answer subtree queries with a path-only implementation.
Variants / Extensions
path xor, min, max, or other associative aggregates,
subtree information by tracking virtual subtrees,
lazy path updates,
dynamic MST or replacement-edge style applications.
The structure stays conceptually the same: expose paths with link-cut operations, and let the auxiliary splay nodes store the right summary.
Practice Problems
Dynamic forest connectivity with link and cut.
Dynamic path sum or xor queries.
Problems where edges appear and disappear over time and the maintained answer depends on tree paths.
References
Code
Contest-ready reference implementation for the idea explained above.
struct LinkCut {
struct Node {
int ch[2] = {0, 0};
int p = 0;
bool rev = false;
long long val = 0, sum = 0;
};
vector<Node> tr;
LinkCut() = default;
explicit LinkCut(int n) : tr(n + 1) {}
bool is_root(int x) const {
int p = tr[x].p;
return p == 0 || (tr[p].ch[0] != x && tr[p].ch[1] != x);
}
void pull(int x) {
tr[x].sum = tr[x].val;
if (tr[x].ch[0]) tr[x].sum += tr[tr[x].ch[0]].sum;
if (tr[x].ch[1]) tr[x].sum += tr[tr[x].ch[1]].sum;
}
void push(int x) {
if (!x || !tr[x].rev) return;
swap(tr[x].ch[0], tr[x].ch[1]);
if (tr[x].ch[0]) tr[tr[x].ch[0]].rev ^= 1;
if (tr[x].ch[1]) tr[tr[x].ch[1]].rev ^= 1;
tr[x].rev = false;
}
void push_path(int x) {
if (!is_root(x)) push_path(tr[x].p);
push(x);
}
void rotate(int x) {
int p = tr[x].p;
int g = tr[p].p;
int dir = (tr[p].ch[1] == x);
int b = tr[x].ch[dir ^ 1];
if (!is_root(p)) tr[g].ch[tr[g].ch[1] == p] = x;
tr[x].p = g;
tr[x].ch[dir ^ 1] = p;
tr[p].p = x;
tr[p].ch[dir] = b;
if (b) tr[b].p = p;
pull(p);
pull(x);
}
void splay(int x) {
push_path(x);
while (!is_root(x)) {
int p = tr[x].p;
int g = tr[p].p;
if (!is_root(p)) {
bool zigzig = (tr[p].ch[0] == x) == (tr[g].ch[0] == p);
rotate(zigzig ? p : x);
}
rotate(x);
}
}
void access(int x) {
int last = 0;
for (int y = x; y; y = tr[y].p) {
splay(y);
tr[y].ch[1] = last;
pull(y);
last = y;
}
splay(x);
}
void make_root(int x) {
access(x);
tr[x].rev ^= 1;
}
int find_root(int x) {
access(x);
while (tr[x].ch[0]) {
push(x);
x = tr[x].ch[0];
}
splay(x);
return x;
}
bool connected(int a, int b) {
return find_root(a) == find_root(b);
}
bool link(int a, int b) {
make_root(a);
if (find_root(b) == a) return false;
tr[a].p = b;
return true;
}
bool cut(int a, int b) {
make_root(a);
access(b);
if (tr[b].ch[0] != a || tr[a].ch[1] != 0) return false;
tr[b].ch[0] = 0;
tr[a].p = 0;
pull(b);
return true;
}
void set_value(int x, long long value) {
access(x);
tr[x].val = value;
pull(x);
}
long long path_sum(int a, int b) {
make_root(a);
access(b);
return tr[b].sum;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.