States that flow upward
Tree DP assigns each node a state computed from its children. A depth first traversal computes child answers first, then merges them at the parent. Maximum independent set on a tree and tree diameter are classic examples.
A worked state
For the maximum independent set, each node keeps two values:
- The best when the node is included, which forbids including its children.
- The best when the node is excluded, which allows children either way.
A parent combines child values: including the parent adds the excluded values of children, while excluding the parent sums the better of each child's two options.
Order of computation
Recurse to leaves first so a parent always has finished child states. Leaves are base cases. The answer for the whole tree is read at the root after the traversal completes.
Key idea
Tree DP computes each node from its already solved children in a post order traversal, often carrying multiple values per node such as included and excluded, and reads the answer at the root.