Link-Cut Trees (LCT) represent an advanced data structure specifically designed to handle dynamic tree problems efficient. By utilizing prefered path decomposition and Splay trees, LCT maintains and manipulates tree structures with logarithmic amortized time complexity for most operations.
Core Concepts
Preferred Path Decomposition
For a given tree T, when a node u undergoes the LCT access operation, we consider u as "visited". For any node u, if the last visited node in its subtree resides within the subtree of one of its children v, we identify v as the preferred child of u. The edge connecting u and v is termed a preferred edge or real edge.
A sequence of continuous real edges forms a preferred path or real chain. It's important to note that preferred children and real chains are not static properties.
LCT maintains these real chains using multiple Splay trees, referred to as auxiliary trees. Each Splay tree contains nodes from a specific real chain, sorted by their depth in the original tree. In other words, the in-order traversal of each Splay tree represents nodes from its corresponding real chain in ascending order of depth.
The edges connecting nodes within the same Splay tree are real edges, while edges connecting different Splay trees are virtual edges.
Basic Operations
LCT supports eight fundamental operations:
- Standard Splay operations: rotate and splay
access(u): Transforms the path from the root to node u into a real chainmake_root(u): Establishes u as the root of the treefind(x): Locates the root of the tree containing xsplit(x, y): Isolates the path between x and y into a separate Splay treecut(x, y): Removes the edge (x, y) from the treelink(x, y): Adds a new tree edge (x, y) to the structure
Detailed Operation Explanations
access Operation
To transform the path from node x to the root into a real chain, we may need to convert some real edges to virtual edges if the path wasn't already a real chain. This involves splitting subtrees connected by these virtual edges into separate Splay trees and connecting them back with virtual edges to the main structure.
The algorithm works by moving from x's Splay tree up to its parent f. For f's right real child, we disconnect it (equivalent to changing the connecting edge to virtual) since we want x to become f's real child. Then we attach x to f's right subtree, effectively extending the real chain.
void access(int x)
{
for (int t = 0; x; t = x, x = parent[x])
{
splay(x);
right_child[x] = t;
update(x);
}
}
make_root Operation
To make node x the root of the tree, we first perform an access operation on x, placing x and the original root in the same real chain (within the same Splay tree). After this operation, x becomes the deepest node in the Splay tree.
We then splay x to become the root of this Splay tree. Since the Splay tree is keyed by depth, swapping the left and right subtrees of each node reverses the depth relationships, effectively flipping the original chain so that x becomes the root.
void make_root(int x)
{
access(x);
splay(x);
reverse[x] ^= 1;
swap(left_child[x], right_child[x]);
}
find Operation
The find operation first accesses the node and then splays it, ensuring the root and the node are in the same real chain. Since the root has the minimum depth and the Splay tree is depth-ordered, the root will be the leftmost node in the Splay tree.
int find(int x)
{
access(x);
splay(x);
while (left_child[x]) x = left_child[x];
return x;
}
split Operation
The split operation assumes that nodes x and y belong to the same tree (are connected in the original tree). First, we make x the root of its tree, then we access y. At this point, x and y are in the same Splay tree with x as the shallowest node (root) and y as the deepest node. The Splay tree contains only nodes between x and y in depth order, which corresponds exactly to the path between them in the original tree.
void split(int x, int y)
{
make_root(x);
access(y);
splay(y);
}
cut Operation
For the cut operation, we first split the path between x and y. If x and y are directly connected, the resulting Splay tree will contain only these two nodes. In this structure, x should be the left child of y with no right child. If x has a right child, it indicates that x and y are connected by a path rather than a direct edge.
This operation performs a bidirectional removal rather than maintaining a one-way relationship like virtual edges.
void cut(int x, int y)
{
split(x, y);
if (left_child[y] == x && !right_child[x])
{
left_child[y] = 0;
parent[x] = 0;
}
}
link Operation
To ensure no nodes above x in its real chain remain unupdated, we first make x the root before directly connecting it to y.
void link(int x, int y)
{
make_root(x);
parent[x] = y;
}
splay Operation
This operation is similar to the standard Splay splay operation, but requires releasing accumulated lazy tags before performing the splay to maintain correct tree structure. Special care must be taken when checking if the current node is a root, as parent pointers may point to nodes in other Splay trees.
void splay(int x)
{
stack[top = 1] = x;
for (int i = x; !is_root(i); i = parent[i]) stack[++top] = parent[i];
for (int i = top; i; i--) push_down(stack[i]);
while (!is_root(x))
{
int y = parent[x], z = parent[y];
if (!is_root(y)) rotate((get(x) == get(y)) ? y : x);
rotate(x);
}
}
is_root Operation
This function determines if node x is the root of its tree within the LCT. If x is a root, the edge connecting it to its parent should be a virtual edge. Virtual edges don't store parent-to-child pointers, so neither of the parent's left or right child pointers should point to x.
bool is_root(int x)
{
return (parent[x] && left_child[parent[x]] != x && right_child[parent[x]] != x);
}
Implementation Example
Below is a complete implementation of LCT supporting path queries and tree modifications:
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, node_value[MAXN];
namespace FastIO {
template<typename t="">
inline void read(T &res) {
res = 0;
bool negative = false;
char ch = getchar();
while ((ch < '0') || (ch > '9')) {
negative |= (ch == '-');
ch = getchar();
}
while ((ch >= '0') && (ch <= '9')) {
res = (res << 3) + (res << 1) + ch - 48;
ch = getchar();
}
res = (negative ? -res : res);
}
template<typename t="">
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
}
using FastIO::read;
using FastIO::write;
struct LinkCutTree {
int node_count, parent[MAXN], left_child[MAXN], right_child[MAXN];
int path_sum[MAXN], traversal_stack[MAXN];
bool reverse_flag[MAXN];
void update(int x) {
path_sum[x] = path_sum[left_child[x]] ^ path_sum[right_child[x]] ^ node_value[x];
}
void push_down(int x) {
if (reverse_flag[x]) {
reverse_flag[left_child[x]] ^= 1;
reverse_flag[right_child[x]] ^= 1;
reverse_flag[x] = false;
swap(left_child[x], right_child[x]);
}
}
int get_direction(int x) {
return right_child[parent[x]] == x;
}
bool is_root(int x) {
return !parent[x] || (left_child[parent[x]] != x && right_child[parent[x]] != x);
}
void rotate(int x) {
int y = parent[x], z = parent[y], dir = get_direction(x);
if (!is_root(y)) {
if (left_child[z] == y) left_child[z] = x;
else if (right_child[z] == y) right_child[z] = x;
}
parent[x] = z;
parent[y] = x;
if (left_child[x] == y) {
left_child[x] = right_child[y];
if (right_child[y]) parent[right_child[y]] = x;
right_child[y] = x;
} else {
right_child[x] = left_child[y];
if (left_child[y]) parent[left_child[y]] = x;
left_child[y] = x;
}
update(y);
update(x);
}
void splay(int x) {
traversal_stack[top = 1] = x;
for (int i = x; !is_root(i); i = parent[i]) traversal_stack[++top] = parent[i];
for (int i = top; i; i--) push_down(traversal_stack[i]);
while (!is_root(x)) {
int y = parent[x], z = parent[y];
if (!is_root(y)) {
if (get_direction(x) == get_direction(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
}
void access(int x) {
for (int last = 0; x; last = x, x = parent[x]) {
splay(x);
right_child[x] = last;
update(x);
}
}
void make_root(int x) {
access(x);
splay(x);
reverse_flag[x] ^= 1;
}
int find_root(int x) {
access(x);
splay(x);
while (left_child[x]) {
push_down(x);
x = left_child[x];
}
splay(x);
return x;
}
void split_path(int x, int y) {
make_root(x);
access(y);
splay(y);
}
void remove_edge(int x, int y) {
split_path(x, y);
if (left_child[y] == x && !right_child[x]) {
left_child[y] = 0;
parent[x] = 0;
}
}
void add_edge(int x, int y) {
make_root(x);
parent[x] = y;
}
void update_value(int x, int new_val) {
access(x);
splay(x);
node_value[x] = new_val;
update(x);
}
} lct;
int main() {
read(n);
read(m);
for (int i = 1; i <= n; i++) {
read(node_value[i]);
lct.path_sum[i] = node_value[i];
}
for (int i = 1; i <= m; i++) {
int op, x, y;
read(op);
read(x);
read(y);
if (op == 0) {
lct.split_path(x, y);
write(lct.path_sum[y]);
putchar('\n');
}
else if (op == 1) {
int root_x = lct.find_root(x);
int root_y = lct.find_root(y);
if (root_x != root_y) lct.add_edge(x, y);
}
else if (op == 2) {
int root_x = lct.find_root(x);
int root_y = lct.find_root(y);
if (root_x == root_y) lct.remove_edge(x, y);
}
else {
lct.update_value(x, y);
}
}
return 0;
}</typename></typename></iostream></cstdio>