Splay Tree Tutorial Implementation Link Cut Tree - Connectivity Tutorial Implementation Link Cut Tree - Paths Implementation Problems Link Cut Tree - Subtrees Tutorial Implementation Problems Edit on Github

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 on Github

Splay Tree

Tutorial

Implementation

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

(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.

Feel free to file a request to complete this using the "Contact Us" button.

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
CSES	CEOI - Treasure Hunt	Normal	Show Tags LCT	View Solution
CF	Baltic OI - 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	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!

Give Us Feedback on Link Cut Tree!

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!

Give Us Feedback on Link Cut Tree!

Module Progress: