树形DP
定义
树形DP，顾名思义是在树上的DP,应用于树形结构的动态规划。
其核心思想是在树的节点间传递和合并状态信息，逐步计算出所需的最优解。
因为树的递归性质，树形动态规划一般都是递归求解的。
经典题目
P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
以这个题目为例，我们定义 $f[i][0/1]$ 来表示以 $i$ 为根的子树的最优解，$f[i][0]$ 代表不选 $i$ 节点，$f[i][1]$ 代表选 $i$ 节点。
所以我们根据 $i$ 节点参不参加分为两种情况:
- $i$ 节点不参加，那么 $i$ 节点的子节点可以参加也可以不参加,所以有 $f[i][0] = \sum{}^{}max(f[j][1],f[j][0])$
- $i$ 节点参加，那么 $i$ 节点的子节点不能参加，所以有 $f[i][1] = \sum{}^{}f[j][0] + w_i$
所以我们可以通过$dfs$ 从最底层向上$dp$