Intro

So far, your DP (dynamic programming) states lived on arrays or grids. Trees are different. States live at nodes, and the answer at each node depends on its children.

I'll show you how to think about DP on trees. You'll learn the post-order DFS pattern that makes tree DP work, and apply it to classic problems: finding the longest path, finding the largest node selection, and computing answers for every possible root. By the end, you'll know how to set up $dp[\text{node}]$ and combine children's values to solve tree problems.