【树形DP】树形DP入门详解+例题剖析

树形DP

树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。整体的思路大致就是用树形的结构存储数据。

要学树形DP之前肯定是要先学会树和图的呀，至少先学会链式前向星，不会的话可以看一下我之前写的博客
链接：【图论】图，实现图（三种方式），二分图 详解

树形DP的关键和实现方法是$dfs$。

先找到树根，从树根开始运用 $dfs$ 递归，跟$dfs$一样先初始化，然后递归到叶子节点上为止，把最底层的 $f[i][j]$ 更新完毕，再回来往上走，自底向上地根据题意更新上层的$f$数组，最后输出答案即可。

一般基础的题转移方程有两种模式：
选择节点类

{ f [ i ] [ 0 ] = f [ j ] [ 1 ] f [ i ] [ 1 ] = max ⁡ / min ⁡ ( f [ j ] [ 0 ] , f [ j ] [ 1 ] )

$$\begin{cases}f[i][0]=f[j][1]\\f[i][1]=\max/\min(f[j][0],f[j][1])\\\end{cases}$$ { f[i][0]=f[j][1]f[i][1]=max/min(f[j][0],f[j][1])​

选择节点式的题首先前提条件是整个数据是由树形结构存储的，或者应该用树形结构存，效率更高什么的，然后会告诉你相邻的节点是不能同时存在的，要求取最大最小值 ，类似P2016 战略游戏、P1352 没有上司的舞会（下面都有详解和题目链接哦）

树形背包类

{ f [ v ] [ k ] = f [ u ] [ k ] + v a l f [ u ] [ k ] = m a x ( f [ u ] [ k ] , f [ v ] [ k − 1 ] )

$$\begin{cases}f[v][k]=f[u][k]+val\\f[u][k]=max(f[u][k],f[v][k-1])\\\end{cases}$$ { f[v][k]=f[u][k]+valf[u][k]=max(f[u][k],f[v][k−1])​
树形背包，就是背包加上条件，一个物品只有选择了它的主件（根节点）才能选择，类似$P2014[CTSC1997]$选课

例题1、P1352 没有上司的舞会

P1352 没有上司的舞会

最基础的入门题，用链式前向星建树，直接用上面总结的转移方程

{ f [ u ] [ 0 ] + = m a x ( f [ v ] [ 0 ] , f [ v ] [ 1 ] ) ; u 不 去 ， 那 么 它 的 子 节 点 （ 下 属 ） 可 去 可 不 去 ， 取 最 大 值 即 可 f [ u ] [ 1 ] + = f [ v ] [ 0 ] ; u 去 了 那 么 它 的 子 节 点 一 定 不 能 去 ， 直 接 加

$$\begin{cases}f[u][0]+=max(f[v][0],f[v][1]);u不去，那么它的子节点（下属）可去可不去，取最大值即可\\f[u][1]+=f[v][0];u去了那么它的子节点一定不能去，直接加\\\end{cases}$$ {