DP on Trees computes optimal solutions for tree problems where the answer for a node depends on its subtree. Classic problems include: maximum independent set on tree, tree diameter, counting paths, and rerooting technique. The DP state is defined per node and transitions come from children.
// Maximum independent set on tree
vector<array<int,2>> dp;
void dfs(int v, int p, vector<vector<int>>& adj, vector<int>& val) {
dp[v][1]=val[v]; dp[v][0]=0;
for(int u:adj[v]) {
if(u==p) continue;
dfs(u,v,adj,val);
dp[v][1]+=dp[u][0];
dp[v][0]+=max(dp[u][0],dp[u][1]);
}
}Root the tree at node 0. For each node v, compute dp[v] using values from its children after they are fully processed. DFS post-order ensures children are computed before parents.
dp[v][1] = max value in subtree of v when v is included. dp[v][0] = max value when v is excluded. If v is included, no children can be included. If v is excluded, each child takes its best option.
The diameter (longest path) can be found with DP: for each node, the longest path through it is (longest path in left subtree) + (longest path in right subtree). Track the global max.
When the DP answer depends on the entire tree (not just subtree), rerooting computes dp for every node as the root in O(n) total by reusing parent computation in a second DFS pass.
Quiz coming soon for this algorithm.