Pattern Guide
Tree DP on General Trees
"DP on trees with arbitrary number of children. Subtree properties, rerooting."
Tree DP on general (non-binary) trees uses DFS post-order: compute dp[node] from dp[children]. Common patterns: max independent set on tree (include/exclude each node), minimum vertex cover, maximum matching, sum of distances in tree (rerooting trick). Rerooting: compute dp[root] first, then re-root at each node using the parent's value to avoid O(n²) recomputation.
Problems you can solve with this pattern
3 problems · click any to start solving
// Maximum independent set on tree
// dp[v][0] = max set size if v NOT included
// dp[v][1] = max set size if v IS included
function maxIndependentSet(n, adj, root = 0) {
const dp = Array.from({length: n}, () => [0, 1]); // [not_taken, taken]
function dfs(v, parent) {
for (const u of adj[v]) {
if (u === parent) continue;
dfs(u, v);
dp[v][0] += Math.max(dp[u][0], dp[u][1]); // v not taken: take best of child
dp[v][1] += dp[u][0]; // v taken: child must not be taken
}
}
dfs(root, -1);
return Math.max(dp[root][0], dp[root][1]);
}Tree DP post-order: solve children first, combine for parent. Max independent set: dp[v][0] = sum(max(dp[c][0], dp[c][1]) for children c), dp[v][1] = 1 + sum(dp[c][0] for children c). Rerooting: first pass computes dp[v][down] (contribution from subtree below). Second pass computes dp[v][full] using parent's contribution. Avoids repeating subtree computations.
// Maximum independent set on tree
// dp[v][0] = max set size if v NOT included
// dp[v][1] = max set size if v IS included
function maxIndependentSet(n, adj, root = 0) {
const dp = Array.from({length: n}, () => [0, 1]); // [not_taken, taken]
function dfs(v, parent) {
for (const u of adj[v]) {
if (u === parent) continue;
dfs(u, v);
dp[v][0] += Math.max(dp[u][0], dp[u][1]); // v not taken: take best of child
dp[v][1] += dp[u][0]; // v taken: child must not be taken
}
}
dfs(root, -1);
return Math.max(dp[root][0], dp[root][1]);
}Rerooting technique: When the answer for every node as root is needed, avoid O(n²) by:
1. First DFS: compute answer for root 0 (subtree-only)
2. Second DFS: when re-rooting to child c from parent p, update: ans[c] = ans[p] + (contribution change)
The contribution change is typically ±1 per node that's "above" vs "below" after the re-root.
3-state DP trick: For coverage/domination problems on trees, states are: uncovered (needs parent to cover), covered by child, has placed element (covers parent).