DP on trees

A tree is a branching structure with no cycles — a family tree, a file system, a road network with no loops. Many questions about a tree have a beautifully recursive flavour: the answer for a node depends only on the answers for its children, which depend on their children, and so on down to the leaves. DP on trees exploits exactly this. Instead of indexing your table by a position in an array, you index it by a node, and the answer for a node is assembled from the answers already computed for the subtrees hanging beneath it.

The recipe is: root the tree anywhere, then process nodes so every child is finished before its parent — a post-order traversal (a DFS that combines results as it returns). Define dp[v] as the best answer for the subtree rooted at node v, and write the transition that builds dp[v] from the dp values of v's children. Often you need two states per node to handle a choice 'is v included or not'. The classic example is the maximum independent set on a tree (largest set of nodes with no two adjacent): let dp[v][0] be the best for v's subtree with v not taken, and dp[v][1] the best with v taken. Then dp[v][1] = 1 + sum over children c of dp[c][0] (if you take v, you cannot take its children), and dp[v][0] = sum over children c of max(dp[c][0], dp[c][1]) (if you skip v, each child is free to be taken or not). The answer is max(dp[root][0], dp[root][1]).

Because each node and each parent-child edge is touched a constant number of times, a tree DP usually runs in O(n) time (or O(n times the per-node state work) for richer states), which is wonderfully cheap. It shows up everywhere trees appear: subtree sizes, longest path, counting matchings, choosing a subset of nodes under adjacency rules. The natural limitation is that the recurrence must be local — dp[v] expressible from children only. When you also need each node's answer 'looking outward' through its parent (not just downward into its subtree), one rooting is not enough, and you reach for the rerooting technique.