状态设计

基本上每一种 dp 都有一种标准的 dp 定义方式，树形 dp 也是如此：

定义 \(f[u]\) 表示以 \(u\) 为根节点的子树里最优的决策。

从分析子树入手，转移便是找到某一子树中，根节点与各子树、边权间的递推关系。

最优解常常是关于根节点的函数。

它的子结构是一颗子树。

实现方式

树形 dp 的实现一般是依靠树的后序遍历（先子节点，后根节点）为理论依据。

算法落到实处，便是运用 dfs 的方式实现。

先从根到叶，然后从叶到根来递推。

经典套路

• 把某个节点的状态加入 dp 数组，如 没有上司的舞会，设计 \(f[u][0/1]\) 表示某个节点选不选进去。
• 把树形 dp 与背包结合，把选 \(i\) 个物品加入 dp 数组，如 二叉苹果树 ，设计 \(f[u][i]\) 表示在 \(u\) 为根节点的子树中，选 \(i\) 条边最大的权值和，按背包来转移，注意边界特判；选课，树形背包模板题。

易错点

• 在某一子树时，设 \(f[u][i]\) 表示以 \(u\) 为根节点的子树里选 \(i\) 个节点的最优解。此时如果以 \(u\) 为根节点的子树里没有 \(i\) 那么多的节点，就会导致转移错误或越界，所以必须特判排除这种情况。