树形DP 学习笔记

模板及讲解

树上背包
问题:给$n$个物品,物品之间有依赖关系,每个物品有重量$w_i$和价值$v_i$,求取物品的最大价值。
解:给定的是一个森林,我们要把森林的根节点全部连到$0$号节点,然后树形DP,设$dp(u, i)$为以$u$为根的子树必选$u$选$i$重量的物品时的最大价值,那么$dp(u, i) = dp(u, i-j) + dp(v, j)$,之后因为要必选$u$,所以大于$w_u$的$i$的$dp(u, i) = dp(u, i-w_u) + v_u$,小于$w_u$的$i$的$dp(u,i) = 0$.
树的重心(质心)
问题:求出一棵无根树的某个点,使得这个点当做根以后最大子树的节点数最小
解:求出每棵树的子树节点数$siz_u$,每个节点作为根时深度$blc=max(siz_v, n-siz_u)$,$v \in son(u)$,然后答案就是$min(blc)$
树的直径(最长路径, 最远点对)
问题:
解:
树的最大独立集
问题:
解:
环套树DP
问题:给定$n$个点,$n$条边,保证任意两点间至少存在一条路径。其中每个点均有其权值$v_i$,问如何选择点,使得在保证任意直接相连的两点不会同时被选中的情况下,被选中的点的权值和最大?
解:对于一棵$n$个节点的树,必然有$n-1$条边,对于一个$n$个点$n$条边构成环的图,我们可以断开这条使得树变成环的边,然后用树形DP设$dp(u,0)$为以$u$为根的子树的最大权和并且不能选$u$, $dp(u,0)$为以$u$为根的子树的最大权和并且必选$u$。然后就对这条边的两个顶点进行两次树形DP,答案就是$max(dp(u, 0), dp(v, 0))$。(第一个是第一次DP的结果,第二个是第二次DP的结果)。为什么要进行两次DP呢,因为如果我们只DP$u$,那么选$u$的方案就不能得到(如果取01最大值,那样会有可能$u, v$同选,不满足题意),就会漏解。

常见题型
1、常规树形DP
Q: 在树上的DP。
解: 通常用dfs完成,从叶子推到根。
例题: Bzoj 1369
2、树上背包
Q: 见讲解
解: 见讲解
例题: Bzoj 2427
3、求树的重心
Q: 见讲解
解: 见讲解
例题: Poj 1655
4、求树的直径
Q: 见讲解
解: 见讲解
例题:
5、求树的最大独立集
Q: 见讲解
解: 见讲解
例题:
6、环套树DP(标志:$n$个点$n$条边)
Q: 见讲解
解: 见讲解
例题: Bzoj 1040
7、树上选点覆盖
Q: Bzoj 1596
解:$f(u, 0)$为不在$u$建基站,$u$与$u$的子树都有信号。$f(u, 1)$为在$u$建基站,$u$与$u$的子树都有信号。$f(u, 2)$为不在$u$建基站,$u$没有信号,$u$的子树都有信号。
例题: Bzoj 1596

------ 本文结束 ------