Graphs -> Link-Cut Tree¶

Dynamic-forest path structure for online link/cut, connectivity, and path aggregates on one changing tree forest.

Microtopics¶

Source	Type
Sleator and Tarjan - A Data Structure for Dynamic Trees	`Primary`
USACO Guide Link Cut Tree	`Reference`
OI Wiki Link-Cut Tree	`Reference`

Source	Type
Library Checker Dynamic Tree Vertex Add Path Sum	`Practice`
Library Checker Dynamic Tree Vertex Set Path Composite	`Practice`

Material	Type
Link-Cut Tree hot sheet	`quick reference`
Link-Cut starter route	`starter route`
Dynamic Tree Vertex Add Path Sum note	`anchor note`
Splay Tree tutorial	`bridge topic`
Heavy-Light Decomposition tutorial	`compare point`
Euler Tour / Subtree Queries tutorial	`compare point`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dynamic Tree Vertex Add Path Sum	`Library Checker`	`Very Hard`	Dynamic Trees	Dynamic Trees; Path Aggregate; Verifier	Rooted Tree Intuition; Preferred Paths; Makeroot / Access	Dynamic Forest; Path Sum; Vertex Add	The cleanest exact verifier for the first narrow link-cut route: dynamic forest, point add on vertices, and path sums.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dynamic Tree Vertex Set Path Composite	`Library Checker`	`Very Hard`	Dynamic Trees	Dynamic Trees; Non-Commutative Query; Verifier	Link-Cut Tree; Path Query Ordering; Function Composition	Dynamic Forest; Path Composite; Non-Commutative	A natural stretch once the basic route is trusted and the path aggregate becomes non-commutative.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`DYNAMICTREEVERTEXADDPATHSUM`	Dynamic Tree Vertex Add Path Sum	`primary`	`very hard`	-	Note	Code

python3 scripts/generate_problem_catalog.py