Skip to content

Graphs -> Tree DP

Tree-rooted dynamic programming from local subtree states to rerooting and path decomposition.

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

Microtopics

  • subtree-dp
  • rerooting
  • independent-set
  • tree-knapsack
  • diameter-dp
  • states-on-rooting

Learning Sources

Source Type
MIT 6.006 structural DP on trees Course
OI Wiki tree DP Reference
USACO Guide DP on trees Reference

Practice Sources

Source Type
CSES Problem Set Practice
USACO contest archive Practice
IOI tasks archive Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Choosing Capital for Treeland Codeforces Medium Rerooting, Tree DP On Directed Edges One Reroot Pass; Edge-Cost Delta Tree Traversal; Edge Orientation Counts Directed Tree Re-rooting the tree changes the inversion count by one edge at a time.
Tree Distances I CSES Medium Rerooting Two DFS Passes; Diameter Endpoints Tree Diameter Intuition; Distance Propagation Distance Standard rerooting practice for maximum distance from every node.
Tree Distances II CSES Hard Rerooting Subtree Sums; Rerooting Formulas Subtree Sizes; Distance Sum Identities Distance Sums; Sum Of Distances Classic rerooting DP on trees.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Independent Set AtCoder DP Contest Medium Coloring DP Bottom-Up DFS; Two-State DP Rooted Tree; State Design; Modular Arithmetic Mod Arithmetic Canonical tree DP where each node keeps take/skip states.
Tree Matching CSES Medium Matching On Trees Postorder DFS; Local State Merge Rooted Tree DP; Independent-Edge Choices Matching; Matching DP; States Classic tree DP for maximum matching on a tree.

Advanced

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Subtree AtCoder DP Contest Hard Rerooting Prefix/Suffix Rerooting; Subtree Products Rooted Tree; Subtree Aggregation; Modular Arithmetic Mod Arithmetic; Mod DP; Rooted Tree; Independent Set The go-to rerooting pattern for answering every root.
Zero Tree Codeforces Hard Difference Accumulation Postorder Balancing; Sign-Aware Subtree Merge Rooted Tree; Subtree Contributions Greedy A strong tree DP where subtree balances determine the answer.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
VOSTRIP VOSTRIP primary hard tree endpoint pairing; path decomposition; local imbalance formula Note Code

Regeneration

python3 scripts/generate_problem_catalog.py