Tree DP
1、基础树形 DP
树形 DP 处理的问题是在树上计算某值的最优解(如最小值)或方案数等问题,通常会有父子节点之间的关系作为限制条件。
譬如说,要在树上选一些点,要求对任意点不能同时选择它和它的父节点,求选出的点的最大点权和。这就是一个典型的树上 DP 问题。
通常来说,我们设计的状态是:$dp[u][…]$
它的含义是,以 $u$ 为根节点的子树中,满足某条件的某值。后面的省略号代表还会有其他的维数,具体因题目而异。
在转移的时候,通常有两种方法:
- 每个节点的 DP 值是由其父节点的 DP 值推出来的。
- 每个节点的 DP 值是由其各个子树的 DP 值合并而来的。
这两种方法都需要用 DFS 来实现。
1 | |
这个 DFS 的框架与正常 DFS 无异,注意的是注释 1 ,2 和 3 处。
注释 1 处理的第一种情况,即每个节点的 DP 值是由其父节点的 DP 值推出来的。此时节点 u 的 DP 值已经算出来了,这里就是处理 v 的 DP 值。
注释 2 处理的第二种情况,即每个节点的 DP 值是由其各个子树的 DP 值合并而来的。此时前面已经递归完了,也就是说 u 的子树里的所有节点的 DP 值都算出来了,在这里合并子树中的信息,得到 u 的 DP 值。
可以发现,第二种情况的实质是从叶子反着推回根,所以我们需要初始化叶子节点。而注释 3 就是实现这一功能的地方,有些时候别的节点也需要初始化。
对于前面说的那个在树上选一些点,要求对任意点不能同时选择它和它的父节点,求选出的点的最大点权和的问题,代码就是这样的:
1 | |
$dp[u][0/1]$ 为:以 $u$ 为根的子树中,不选/选节点 $u$ 的最大点权和。
2. 树上背包
例题:在树上选 $m$ 个节点,如果选择了某个节点,那么它的父节点也必须选,求选出的 $m$ 个节点的最大点权和
与正常的一维背包相似,设 $dp[u][i][j]$ 为:以 $u$ 为根的前 $i$ 个子树内选 $j$ 个节点的最大点权和。
滚动数组可以将那个“$[i]$”优化掉。
1 | |
$s$ 是点权。此处类似于多重背包,需要枚举以 $v$ 为根的子树中选几个节点。
3. 换根 DP
此时根不固定,考虑对于每个节点,当它为根时,某值是怎样的。
例题:给定一个 $n$ 个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大。一个结点的深度之定义为该节点到根的简单路径上边的数量。
我们的思路是:做 2 个 DFS。
还是假定 1 为根
第一个 DFS 处理出 $dp_1$,即以 1 为根时所有点的深度,然后再处理出以 1 为根时,每个节点子树的大小(设 $cnt_i$ 为以 $i$ 为根的子树的大小)。
在第二个 DFS 中,考虑当 $dp_u$ 确定了之后,如何算出 $dp_v$,其中 $v$ 是 $u$ 的儿子,两节点之间的边权为 $w$。
我们发现,当根从 $u$ 转到 $v$ 时,$v$ 的子树内的所有节点(共 $cnt_v$ 个)的深度都会减少 $w$,因为它们距离 $v$ 比距离 $u$ 近了 $w$。而不在 $v$ 的子树内的节点(共 $n-cnt_v$ 个)的深度都会增加 $w$,因为它们距离 $v$ 比距离 $u$ 远了 $w$。
所以,$dp_v=dp_u-w\times cnt_v+w\times (n-cnt_v)$
代码如下
1 | |
注意,第一个 DFS 执行完之后,先算出 $dp_1$ 的值,再执行第二个 DFS。