Splay Tree Tutorial Implementation Link Cut Tree - Connectivity Tutorial Implementation Link Cut Tree - Paths Implementation Problems Link Cut Tree - Subtrees Tutorial Implementation Problems Edit with LiveUpdate

Rare

0/19

Link Cut Tree

Author: Benjamin Qi

Prerequisites

Splay Tree Tutorial Implementation Link Cut Tree - Connectivity Tutorial Implementation Link Cut Tree - Paths Implementation Problems Link Cut Tree - Subtrees Tutorial Implementation Problems

Edit with LiveUpdate

Splay Tree

Tutorial

Implementation

This section is not complete.

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

(Related?)

Euler Tour Tree

Link Cut Tree - Connectivity

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

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	SPOJ	Dynamic Connectivity	Very Easy	Show Tags LCT	Show Sketch

Tutorial

Implementation

This section is not complete.

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

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	CF	Silence's Sounds	Easy	Show Tags LCT	Check CF
	SPOJ	Dynamic LCA	Normal	Show Tags LCT	View Solution

Link Cut Tree - Paths

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	YS	Vertex Add Path Sum	Easy	Show Tags LCT	View Solution

Implementation

Problems

Source	Problem Name	Difficulty	Tags	Solution
YS	Vertex Add Path Composite	Easy	Show Tags LCT	View Solution
DMOJ	Squirrel Cities	Normal	Show Tags LCT	Check DMOJ
HR	Balanced Tokens	Normal	Show Tags LCT	Check HR
CEOI	2011 - Treasure Hunt	Normal	Show Tags LCT	View Solution
Baltic OI	2020 - Joker	Hard	Show Tags LCT	Check CF
DMOJ	Dynamic Tree Test (Easy)	Hard	Show Tags LCT	Check DMOJ
CF	Train Tracking	Hard	Show Tags LCT	Check CF
CF	Tree or not Tree	Hard	Show Tags LCT	Check CF
CF	CERC 17 D	Hard	Show Tags LCT	Check CF
IOI	2011 - Dancing Elephants	Hard		External Sol

Link Cut Tree - Subtrees

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	YS	Vertex Add Subtree Sum	Normal	Show Tags LCT	View Solution

Tutorial

Resources
CF	ouuan - Maintaining Subtree Info

Implementation

Resources
Benq	LCT

Problems

Source	Problem Name	Difficulty	Tags	Solution
CF	Pastoral Oddities	Normal	Show Tags LCT	Check CF
YS	Subtree Add Subtree Sum	Hard	Show Tags LCT	View Solution
CF	Old Driver Tree	Very Hard	Show Tags LCT	Check CF
DMOJ	Dynamic Tree Test	Very Hard	Show Tags LCT	Check DMOJ

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

Table of Contents

Link Cut Tree

Prerequisites

Table of Contents

Splay Tree

Tutorial

Implementation

This section is not complete.

Link Cut Tree - Connectivity

Tutorial

Implementation

This section is not complete.

Link Cut Tree - Paths

Implementation

Problems

Link Cut Tree - Subtrees

Tutorial

Implementation

Problems

Module Progress:

Join the USACO Forum!

Table of Contents

Link Cut Tree

Prerequisites

Table of Contents

Splay Tree

Tutorial

Implementation

This section is not complete.

Link Cut Tree - Connectivity

Tutorial

Implementation

This section is not complete.

Link Cut Tree - Paths

Implementation

Problems

Link Cut Tree - Subtrees

Tutorial

Implementation

Problems

Module Progress:Not Started

Join the USACO Forum!

Module Progress: