树形动规

树形DP

前言:

通常的动态规划都是在有向无环图上进行的,无论是线性的还是树形细想:假如有环的话必定没有一个特定的递推顺序,背包问题一般都是线性上的动态规划,我们这里开始了解简单的树形dp。

树形动态规划就是在“树”这种特殊的数据结构上进行的动态规划 ,树形dp通常有两种方向 一种是自顶向下 一种是自底向上

(1)叶—-> 根 :在回溯的时候从叶子结点往上更新信息(没有上司的舞会)
(2)根—-> 叶 :往往是在从叶往根dfs一遍之后,相当于预处理,再重新往下获取最后的答案
树形dp往往都是要利用递归的写法来实现的 dfs
而视题目建立有向图还是无向图 可以减少代码量
没有上司的舞会

题目大意:每个结点给定一个价值,子节点和父亲结点不能同时选取,求能够选取的最大价值

转移方程:
f[u][0]:表示不选择u结点后u子树能够得到的最大值
f[u][1]:表示选择u结点后u子树的能够得到的最大值

$$
f[u][0]=\sum max\{f[u][0],f[u][1]\}
f[u][1]=a[u]+\sum f[u][0]
$$.

 
华丽的吊灯
again:
$$
f[i][j]=max\{ f[i][j-k-w[son] ] + f[son][k] + l[son] \}
$$.

 
拓扑序计数
$$
f[i]=\frac{(size(i)-1)!}{\prod (s[j]!)(j\epsilon son[i])}*\prod f[j],j\epsilon son[i]
$$.
相当于从(size[i]-1)个中取s[j]个的排列组合。
注意有模P以及涉及除法,先处理出逆元。