Dynamic Programming on Trees

A tree naturally breaks a problem into independent sub-problems: whatever the answer is for a node, it usually depends only on the answers already computed for its children, never on some other unrelated branch. Dynamic programming on trees exploits this by doing a post-order traversal — visit every child before its parent — and storing one or a few numbers at each node that summarize everything an ancestor needs to know about the subtree below it, so the parent never has to re-examine the whole subtree itself.

A classic example is finding the maximum independent set of nodes in a tree (no two chosen nodes connected by an edge) to maximize a total weight. At each node, track two values: the best score if this node is included, and the best score if it's excluded. If included, its children must be excluded, so the node's "included" score is its own weight plus each child's "excluded" score; its "excluded" score is simply the sum of each child's better option (included or excluded, whichever is larger). Computing these bottom-up means each node is visited once and its answer is ready by the time its parent needs it, giving an overall running time linear in the number of nodes rather than the exponential blow-up of checking every subset directly.