树形 DP 学习笔记
声明
给出的连接主要是看一下它的代码
自认为很好的题就被标粗,前面加了 √ 辣!并被我放大咯!
树形 DP
树形 DP 和线性的最大区别就是:DP 的顺序是有讲究的,要先 DP 儿子。
如何保证 DP 该点之前子节点已经被 DP 过了呢?
我们可以直接在 DFS 的过程中 DP,DP 时用到了子节点的话就先 DFS 一遍子节点。
【这样特殊在于这种 DFS,不返回一个特定状态值,而是把儿子的所有状态值计算了】
这样就不会出现 DP 顺序的错误辣~(≧▽≦)/~
P.S. 当然也有一类题目的转移是由父亲转移到儿子的,这类题目少见但是经典。
1. 树形背包——有依赖性的背包问题
这一类问题的状态一般为
f[i][j] 表示以i 为根的子树 状态为j 时。
–
√【Luogu P2014 选课】【树形背包学习笔记】
这个是精♂妙的理解部分:
然后就是分组背包,每组只能选一个物品,要使价值最大,也就是对于每组枚举选几件和枚举体积。
–
–
二叉苹果树
–
【Luogu P1270】“访问”美术馆 —— By 安好
(注意代码
递归建树。
注意要减去经过走廊时间,一去一回要乘二,直接在最开始乘就好了。
2. 每个点的状态较少:f[u][0/1/2…]
【CODEVS1380】没有上司的舞会 —— By Robot
设
如果
–
√ 【BZOJ1907】树的路径覆盖 —— By zyf2000
对于每个节点
(巧妙的状态表示!
这题感觉转移是难点呀 … 还是 Kumii 太弱了>_<
- 当前点是转折点:
·当前点是转折点,并且所有儿子也都是转折点
(比如以 4 为根的子树) 或当前点不是转折点,其中一个儿子也不是转折点,当前点与这个儿子连成转折点
(这种情况只有当经过当前转折点的链 与 枚举的不是转折点的儿子的链 不重合时) - 当前点是非转折点:
当前点是非转折点,其所有儿子都是转折点
(当前点与其父亲向上组成链) 或当前点是非转折点,其儿子中有一个为非转折点,当前点与这个儿子组成一条链,其他儿子是转折点
(比如以 2 为根子树)。f[u][1]=min(f[u][1]+f[v][0],tmp+f[v][1])
注意:第二种转移的第二种情况是只有当前枚举的这个儿子是非转折点,其他儿子都为转折点,所以要记一个tmp 是之前枚举过的儿子是转折点的最小路径覆盖数。