DP -> Tree DP

DP on rooted trees, rerooting, subtree merges, and local state design for hierarchical structures.

• Topic slug: dp/tree-dp
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 3
• Repo companion pages: 0
• Curated external problems: 10

Microtopics

• subtree-dp
• include-exclude
• rerooting
• tree-knapsack
• merge-small-to-large-dp
• edge-vs-node-states

Learning Sources

Source	Type
USACO Guide DP on Trees	Reference
OI Wiki tree DP	Reference
USACO Guide Combining Subtrees	Reference

Practice Sources

Source	Type
AtCoder DP P	Practice
CSES Tree Matching	Practice

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Matching	CSES	Medium	-	-	-	Matching	child-combination DP on trees
Subtree	AtCoder DP Contest	Medium-Hard	-	-	-	Rerooting	rerooting / subtree accumulation

All Roots Distance DP

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sum of Distances in Tree	LeetCode	Hard	Rerooting	DFS; Rerooting	Subtree Sizes; Tree Traversal	-	A very common rerooting problem that teaches how to propagate global answers across all nodes.

Best Path Through A Node

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Binary Tree Maximum Path Sum	LeetCode	Hard	Path-Aggregation	DFS; Postorder	Tree Recursion; Max Subarray Intuition	Path	A classic tree aggregation problem where each node contributes one-sided path values upward.

Maximum Distance Per Node

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Distances I	CSES	Medium	Rerooting	DFS; Rerooting	Tree Traversal; DFS Order	Distance	A clean rerooting example that asks for a per-node aggregate over the whole tree.

Root Choice Optimization

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Directory Traversal	USACO Gold	Medium	Rerooting	DFS; Rerooting	Tree Distance Basics; Prefix Sums	-	A great rerooting-style tree DP where the answer depends on where you stand in the tree.

Sum Of Distances

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Distances II	CSES	Medium	Rerooting	DFS; Rerooting	Tree Distances I; Subtree Sizes	-	The sum-of-distances sibling to Tree Distances I, and a classic rerooting benchmark.

Tree Coloring

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Barn Painting	USACO Gold	Easy	Coloring-DP	DFS; Postorder	Tree Traversal; State Compression	Coloring	A classic colored-tree DP that cleanly illustrates parent-state dependency.

Tree Independent Set

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Independent Set	AtCoder DP Contest	Medium	Subtree-DP	DFS; Postorder	Tree Traversal; Basic Recursion	Independent-Set; 2-State	The textbook tree DP for choosing or skipping each node under parent-child constraints.

Tree Skip Take

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
House Robber III	LeetCode	Medium	Tree-Structure	DFS; Postorder	Binary Tree Traversal; State Pairs	Binary-Tree; Skip-Take	A highly recognizable tree DP where each node returns take and skip values.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
TREEDISTANCES2	Tree Distances II	primary	medium	-	Note	Code
TREEMATCHING	Tree Matching	primary	medium	tree matching dp; matched or unmatched state; child swap contribution	Note	Code
VOSTRIP	VOSTRIP	secondary	hard	tree endpoint pairing; path decomposition; local imbalance formula	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py