Tree DP Pattern
Root the tree at an arbitrary node (usually 0). Run a DFS. For each node,
compute dp[node] from dp[child] of all its children.
The DFS post-order ensures children are processed before their parent.
C++ — tree DP template (subtree size)
vector> adj;
vector dp;
void dfs(int u, int parent) {
dp[u] = 1; // count this node
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
dp[u] += dp[v]; // add child's subtree size
}
}
// Usage: dfs(0, -1)
// dp[u] = size of subtree rooted at u
💡 The parent parameter
Trees don't have cycles, but DFS can still loop back to the parent. Passing
parent and skipping it avoids this. It's the tree equivalent
of a visited array.
C++ — max path sum from root (no re-entry)
int dfs(int u, int parent) {
int best = 0;
for (int v : adj[u]) {
if (v == parent) continue;
best = max(best, dfs(v, u));
}
return 1 + best; // longest downward path
}
Rust — tree DP
fn dfs(u: usize, parent: usize, adj: &[Vec], dp: &mut Vec) {
dp[u] = 1;
for &v in &adj[u] {
if v == parent { continue; }
dfs(v, u, adj, dp);
dp[u] += dp[v];
}
}