Rare
 0/19
Link Cut Tree
Authors: Benjamin Qi, Neo Wang
Dynamic operations on a rooted forest
Splay Tree
Tutorial
Resources | ||||
---|---|---|---|---|
MIT | ||||
Stanford | ||||
CMU | ||||
GH |
Link Cut Tree
Dynamic Connectivity
Focus Problem – read through this problem before continuing!
With Link-Cut Tree
#include <bits/stdc++.h>using namespace std;Code Snippet: Link Cut Tree (Click to expand)int N, M;int main() {cin.tie(0)->sync_with_stdio(0);
With Euler-Tour Tree
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);if (s == "add") {add(A,B);} else if (s == "rem") {
Link Cut Tree - Connectivity
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CF | Easy | Show TagsLCT | |||
SPOJ | Normal | Show TagsLCT |
Link Cut Tree - Paths
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
YS | Easy | Show TagsLCT |
Implementation
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
YS | Easy | Show TagsLCT | |||
DMOJ | Normal | Show TagsLCT | |||
HR | Normal | Show TagsLCT | |||
CEOI | Normal | Show TagsLCT | |||
Baltic OI | Hard | Show TagsLCT | |||
DMOJ | Hard | Show TagsLCT | |||
CF | Hard | Show TagsLCT | |||
CF | Hard | Show TagsLCT | |||
CF | Hard | Show TagsLCT | |||
IOI | Hard |
Link Cut Tree - Subtrees
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
YS | Normal | Show TagsLCT |
Tutorial
Resources | ||||
---|---|---|---|---|
CF |
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CF | Normal | Show TagsLCT | |||
YS | Hard | Show TagsLCT | |||
CF | Very Hard | Show TagsLCT | |||
DMOJ | Very Hard | Show TagsLCT |