Link-Cut Tree Hot Sheet

Use this page when the forest changes online and you still need path connectivity or one path aggregate to stay logarithmic.

Do Not Use When

• the tree is static -> HLD hot sheet or Subtree Queries hot sheet
• queries are rooted-subtree only -> Subtree Queries hot sheet
• updates are offline add/remove events with component-only answers -> DSU Rollback hot sheet
• you are still learning rooted-tree basics or path decomposition from scratch

Choose By Signal

• static tree, repeated path aggregates -> HLD hot sheet
• static rooted subtree interval -> Subtree Queries hot sheet
• static balanced recursive split through one pivot -> Centroid hot sheet
• dynamic forest with link / cut / connected / path-sum -> link-cut tree -> link-cut-tree-path-sum.cpp
• offline connectivity under edge add/remove -> DSU Rollback hot sheet

Core Invariants

• the represented forest and the auxiliary splay trees are different objects
• access(u) exposes one represented root-to-u path
• makeroot(u) is access(u) plus a lazy path reversal
• after makeroot(u) then access(v), the whole path u -> v sits in v's auxiliary tree
• is_root(x) means root of the current auxiliary splay tree, not root of the represented tree

Main Traps

• rotating before pushing reverse flags
• reading auxiliary parents as represented-tree parents
• using LCT for static trees where HLD or Euler flattening is simpler
• overclaiming subtree support from a path-only starter
• forgetting that the exact repo starter is vertex-valued point-add + path-sum

Exact Starter Route

• exact starter -> link-cut-tree-path-sum.cpp
• flagship rep -> Dynamic Tree Vertex Add Path Sum
• machinery refresher -> Splay Tree hot sheet
• static path contrast -> HLD hot sheet
• static subtree contrast -> Subtree Queries hot sheet

Reopen Paths

• full lesson -> Link-Cut Tree
• underlying rotate/splay lane -> Splay Tree
• static path queries instead -> Heavy-Light Decomposition
• subtree-only routing instead -> Euler Tour / Subtree Queries
• graph-family chooser -> Graph cheatsheet
• snippet chooser -> Template Library