Link-Cut Tree Ladder

This ladder is for the first time a tree problem says:

• the forest changes online
• path queries still remain
• rebuilding one static decomposition after each change is no longer acceptable

It is intentionally a thin lane:

• one exact starter
• one verifier-style flagship rep
• strong compare points back to static-tree routes

Who This Is For

Use this lane if:

• Heavy-Light Decomposition already makes sense on static trees
• Euler Tour / Subtree Queries already feels easy when the root and edges stay fixed
• your current problem changes the tree itself and static preprocessing is the thing that breaks

Warm-Up

• static path aggregates -> Path Queries II
• static rooted subtree intervals -> Subtree Queries
• offline dynamic connectivity contrast -> Dynamic Connectivity

Target skill:

• explain clearly why the next problem is not "just harder HLD"

Core

• auxiliary tree vs represented tree
• access, makeroot, find_root
• exact starter route: link-cut-tree-path-sum.cpp
• flagship rep: Dynamic Tree Vertex Add Path Sum

Target skill:

• turn a dynamic-tree statement into makeroot / access / link / cut / path aggregate without guessing

Stretch

• Library Checker - Dynamic Tree Vertex Set Path Composite
• USACO Guide - Link Cut Tree
• OI Wiki - Link-Cut Tree

Target skill:

• know when the exact starter still fits and when the aggregate contract has drifted into non-commutative or more generic territory

Retrieval Layer

• exact quick sheet -> Link-Cut Tree hot sheet
• exact starter -> link-cut-tree-path-sum.cpp
• static-path compare point -> HLD hot sheet
• subtree-only compare point -> Subtree Queries hot sheet
• graph-family chooser -> Graph cheatsheet

Repo Anchors And Compare Points

• topic page -> Link-Cut Tree
• static path compare point -> Heavy-Light Decomposition
• static subtree compare point -> Euler Tour / Subtree Queries
• offline connectivity compare point -> DSU Rollback / Offline Dynamic Connectivity
• broader routing -> Graphs ladder

Exit Criteria

You are ready to move on when:

• you can say why static HLD/Euler flattening are the wrong fit for the query stream
• you understand the difference between represented forest and auxiliary splay tree
• you can explain why makeroot(u) then access(v) exposes the path u -> v
• you can use the starter for one dynamic path-sum problem without treating it as black magic

External Practice

• Library Checker - Dynamic Tree Vertex Add Path Sum
• Library Checker - Dynamic Tree Vertex Set Path Composite
• USACO Guide - Link Cut Tree

Tutorial Link

• Link-Cut Tree