Tree DP
Exploit the parent-child structure of trees so each state only has to summarize one rooted subtree at a time.
Tree DP
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Tree DP works because removing one edge splits the structure cleanly. That means a subtree often carries exactly the local information needed for a recurrence, without the cycles that make general graph DP difficult.
When to Use It
Use tree DP when:
the input is a tree or can be reduced to one,
the answer decomposes naturally across child subtrees,
a parent only needs a summary from each child, not the full internal structure.
Core Idea
Root the tree, then define DP states per vertex. A typical pattern is: \[ dp[v][state] = \text{best answer inside the subtree of } v \text{ under some local condition at } v. \]
Key Insight
The tree structure removes cyclic dependencies. Once the children are solved, their contributions can be merged into the parent's state.
Operations / Main Technique
choose a root,
define a local state at each node,
DFS from leaves upward,
merge child contributions.
Worked example.
For maximum independent set on a tree, use two states:
\(\texttt{take[v]}\): best if \(v\) is chosen,
\(\texttt{skip[v]}\): best if \(v\) is not chosen.
If \(v\) is taken, no child may be taken. If \(v\) is skipped, each child chooses its better state.
Correctness Intuition
Every edge is cut exactly once by the parent-child direction, so a subtree DP can summarize all decisions below a node without ambiguity. The merge step is correct because child subtrees are disjoint except for the parent connection.
Complexity Analysis
Many tree DP routines are \(O(n)\) or \(O(n \log n)\), depending on the merge cost per child.
Implementation
The reference code implements maximum independent set on a tree, which is a clean example of the parent-child state split and the merge logic.
Common Pitfalls
Forgetting to exclude the parent during DFS.
Choosing a state that is too weak and loses necessary information.
Writing an \(O(n^2)\) merge when the state can be simplified.
Variants / Extensions
Rerooting DP.
DP on trees with knapsack-style child merges.
Tree DP after bridge-tree or condensation reductions.
Practice Problems
Maximum independent set on a tree.
Count colorings with parent-child restrictions.
Subtree optimization with one local state per node.
References
Code
Contest-ready reference implementation for the idea explained above.
struct TreeIndependentSet {
vector<vector<int>> tree;
vector<long long> take;
vector<long long> skip;
explicit TreeIndependentSet(int n) : tree(n), take(n, 0), skip(n, 0) {}
void add_edge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
void dfs(int v, int parent = -1) {
take[v] = 1;
skip[v] = 0;
for (int to : tree[v]) {
if (to == parent) continue;
dfs(to, v);
take[v] += skip[to];
skip[v] += max(take[to], skip[to]);
}
}
long long solve(int root = 0) {
dfs(root);
return max(take[root], skip[root]);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.