Rare
 0/19

Link Cut Tree

Authors: Benjamin Qi, Neo Wang

Dynamic operations on a rooted forest

Splay Tree

Tutorial

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

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsLCT
SPOJNormal
Show TagsLCT

Link Cut Tree - Paths

StatusSourceProblem NameDifficultyTags
YSEasy
Show TagsLCT

Implementation

Problems

StatusSourceProblem NameDifficultyTags
YSEasy
Show TagsLCT
DMOJNormal
Show TagsLCT
HRNormal
Show TagsLCT
CEOINormal
Show TagsLCT
Baltic OIHard
Show TagsLCT
DMOJHard
Show TagsLCT
CFHard
Show TagsLCT
CFHard
Show TagsLCT
CFHard
Show TagsLCT
IOIHard

Link Cut Tree - Subtrees

StatusSourceProblem NameDifficultyTags
YSNormal
Show TagsLCT

Tutorial

Problems

StatusSourceProblem NameDifficultyTags
CFNormal
Show TagsLCT
YSHard
Show TagsLCT
CFVery Hard
Show TagsLCT
DMOJVery Hard
Show TagsLCT

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!