Link Cut Tree

Splay Tree

A splay tree is a type of self-balancing binary search tree that supports efficient implementation of operations such as finding an element, deleting an element, splitting a tree, and joining two trees.

When a node in a splay tree is accessed, a splay operation is performed on the node that moves it to the root of the tree while also roughly balancing the tree.

Link Cut Tree

A link cut tree is a data structure that uses splay trees to represent a forest of rooted trees and can perform the following operations with an amortized upper bound time complexity of $\mathcal{O}(\log N)$:

• Linking a tree with a node by making the root of the tree a child of any node of another tree
• Deleting the edge between a node and its parent, detaching the node's subtree to make a new tree
• Find the root of the tree that a node belongs to

These operations all use the $\texttt{access}(v)$ subroutine, which creates a preferred path from the root of the represented tree to vertex $v$, making a corresponding auxiliary splay tree with $v$ as the root.

Solution

With Link Cut Tree

We can use a link cut tree to process each type of query $\mathcal{O}(\log N)$ time. Adding an edge or removing an edge between two vertices are standard features of the link cut tree.

Checking if there's a path between two nodes is the same as checking if they're part of the same tree. To check if two nodes are part of the same tree, we can check if the roots of the trees of the two nodes are the same.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Link Cut Tree (Click to expand)

int main() {
	int n;
	int m;
	cin >> n >> m;
	LCT lc(n);

With Euler Tour Tree

An alternative solution is to use the Euler Tour Tree (ETT) technique, which builds upon our existing Euler tour technique by storing the Euler Tour of the tree in a balanced binary search tree instead of an array.

Copy
 Code Snippet: Benq Template (Click to expand)
 Code Snippet: Euler Tour Tree (Click to expand)

int main() {
	int N, M;
	re(N, M);
	F0R(i, M) {
		str s;
		int A, B;
		re(s, A, B);

Finding Connectivity

The link cut tree can be used to solve problems that deal with queries updating trees and querying for connectivity.

Explanation

The lowest common ancestor of two nodes is found by first making a preferred path from the root to one node and then the other. After we splay the first node, the lowest common ancestor is just the first node's parent.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

 Code Snippet: Benq Link Cut Tree (Click to expand)

const int MAX_N = 1e5;
sn LCT[MAX_N];

Link Cut Tree - Paths

Explanation

An LC Tree can also calculate the aggregate (max, min, sum, etc.) of the weights of the edges or nodes on a path.

To do this, we can define a function that will return an aggregate for the path from the root of the tree to the provided vertex. We can augment the auxiliary splay trees with the value(s) we want to keep track of. The aggregate for the path from the root of a tree to a vertex can be found by retrieving the value(s) from the splay tree created after accessing the vertex.

Implementation

Time Complexity: $\mathcal{O}(Q\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

 Code Snippet: Benq Link Cut Tree (Click to expand)

const int MAX_N = 2e5;
sn LCT[MAX_N];

Problems

Link Cut Tree - Subtrees

Explanation

We can also maintain information about subtrees by keeping track of values for the virtual subtrees of a node. When querying for information such as the subtree sum, we call access on the node so that all of its children in the represented tree are part of virtual subtrees and then retrieve the desired value.

Implementation

Time Complexity: $\mathcal{O}(Q\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

 Code Snippet: Benq Link Cut Tree (Click to expand)

const int MAX_N = 2e5;
sn LCT[MAX_N];

Problems