Auxiliary Tree¶

Compress one marked subset of a static rooted tree into the LCAs and branch points that still matter, then run the real query-local DP on that smaller tree.

Topic slug: graphs/virtual-tree
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 5
Curated external problems: 2

Microtopics¶

marked-subset
dfs-order
consecutive-lca
ancestor-stack
compressed-tree
query-local-dp

Learning Sources¶

Source	Type
OI Wiki virtual tree	`Reference`
Codeforces Round #339 editorial	`Reference`
Codeforces 613D - Kingdom and its Cities	`Practice`

Practice Sources¶

Source	Type
Codeforces problemset	`Practice`
AtCoder problems archive	`Practice`

Repo Companion Material¶

Material	Type
Virtual Tree hot sheet	`quick reference`
Virtual Tree starter route	`starter route`
Kingdom and its Cities note	`anchor note`
LCA tutorial	`prerequisite tutorial`
Tree DP tutorial	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Kingdom and its Cities	`Codeforces`	`Very Hard`	-	Marked-Subset Compression; LCA; Query-Local DP	LCA; DFS Order; Tree DP	Marked Nodes; LCA; Tree DP; Minimum Separator	The classic first full virtual-tree problem: each query marks only a small set, and the whole solution is compress-then-DP.

Stretch¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Leaf Color	`AtCoder`	`Very Hard`	-	Marked-Subset Compression; Per-Color Processing; Tree DP	Virtual Tree Build; LCA; Compressed-Tree Reasoning	Marked Nodes; Color Grouping; Compressed Tree	A strong stretch rep once the build step feels automatic and the real challenge becomes choosing the right summary on the compressed tree.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`KINGDOMANDITSCITIES`	Kingdom and its Cities	`primary`	`very hard`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py