Section Recap

You learned DP on trees. States live at nodes and flow from children to parents via post-order DFS.

$1.$ The pattern: $dp[v]$ combines $dp[\text{child}]$ values. Leaves are base cases.

$2.$ For path problems (diameter), track a global answer for paths passing through each node.

$3.$ For selection problems (House Robber III), track multiple states per node.

$4.$ For "answer at each node" problems, use rerooting: one pass down, one pass up. Tree DP shows up often. The recursive structure of trees makes these problems natural once you see the pattern.