PrevNext
Rare
 0/19

Link Cut Tree

Author: Benjamin Qi

Prerequisites

?

Splay Tree

Tutorial

Implementation

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

(Related?)

Link Cut Tree - Connectivity

Simplest case: test whether two vertices are connected or not.

StatusSourceProblem NameDifficultyTags
SPOJ
Dynamic Connectivity
Very Easy
Show TagsLCT

Tutorial

Implementation

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.
StatusSourceProblem NameDifficultyTags
CF
Silence's Sounds
Easy
Show TagsLCT
SPOJ
Dynamic LCA
Normal
Show TagsLCT

Link Cut Tree - Paths

StatusSourceProblem NameDifficultyTags
YS
Vertex Add Path Sum
Easy
Show TagsLCT

Implementation

Problems

StatusSourceProblem NameDifficultyTags
YS
Vertex Add Path Composite
Easy
Show TagsLCT
DMOJ
Squirrel Cities
Normal
Show TagsLCT
HR
Balanced Tokens
Normal
Show TagsLCT
CEOI
2011 - Treasure Hunt
Normal
Show TagsLCT
Baltic OI
2020 - Joker
Hard
Show TagsLCT
DMOJ
Dynamic Tree Test (Easy)
Hard
Show TagsLCT
CF
Train Tracking
Hard
Show TagsLCT
CF
Tree or not Tree
Hard
Show TagsLCT
CF
CERC 17 D
Hard
Show TagsLCT
IOI
2011 - Dancing Elephants
Hard

Link Cut Tree - Subtrees

StatusSourceProblem NameDifficultyTags
YS
Vertex Add Subtree Sum
Normal
Show TagsLCT

Tutorial

Resources
CF
ouuan - Maintaining Subtree Info

Implementation

Resources
Benq
LCT

Problems

StatusSourceProblem NameDifficultyTags
CF
Pastoral Oddities
Normal
Show TagsLCT
YS
Subtree Add Subtree Sum
Hard
Show TagsLCT
CF
Old Driver Tree
Very Hard
Show TagsLCT
DMOJ
Dynamic Tree Test
Very 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!

Join Forum
PrevNext