树形 DP 总结

树形 DP

树形 DP，就是以树为模型的动态规划。主要利用树本身带来的子结构(树上的父子关系)来进行状态转移。

一般情况下，都是通过子节点的 DP 值来推出父节点的 DP 值。除此之外，经常会通过子节点的一些辅助信息来推出父节点的辅助信息，比如 $s z$ ——子树大小， $s u m$ ——从根节点到子节点的点权/边权和等。

状态设计

常见类型：

注：为了方便阅读，做如下规定：

下文中 $a_{x}$ 统一表示 $x$ 的点权。
$s z_{x}$ 统一表示 $x$ 的子树大小。
$l s o n_{x}$ 和 $r s o n_{x}$ 分别表示 $x$ 的左右儿子。(仅限于二叉树)
$s o n_{x}$ 表示 $x$ 的儿子。
$f a_{x}$ 表示 $x$ 的父亲。
$w (u, v)$ 表示 $u \to v$ 这条边的权值。

以 $d p_{x}$ 表示以 $x$ 为根的答案。

一般 $x$ 的答案可以直接由 $x$ 的儿子转移得到。较为简单。

P1122 最大子树和

定义 $d p_{x}$ 表示以 $x$ 为根的子树中最大的子树权值和是多少。

特征：类比最大子段和，若以 $x$ 儿子为根的 $d p$ 值 $> 0$ ，则说明其对 $x$ 有贡献，反之无贡献，即 $x$ 的 $d p$ 值与其儿子的 $d p$ 值有关。

转移：

$d p_{x} = a_{x} + \sum max (d p_{s o n [x]}, 0)$
以 $d p_{x, 0 / 1}$ 表示以 $x$ 为根的子树， $x$ 选或者不选/ $x$ 是否在某个特定类型中(题目给出)的答案。

首先子结构往往和树上父子关系有关，往往答案与 $x$ 选/不选或者某个题中所给的特定类型有关，且第二维一般表示 $x$ 的状态。详见下述例子。

例：

P1352 没有上司的舞会

定义 $d p_{x, 0 / 1}$ 表示以 $x$ 为根的子树， $x$ 参加/不参加舞会的最大的快乐指数。

特征： $x$ 为根的子树的答案可以由 $x$ 的儿子转移而来， $x$ 的儿子参加或不参加决定了 $x$ 是否参加。

转移：

$x$ 如果参加， $x$ 的儿子参加或者不参加都行。

$x$ 如果不参加，那么 $x$ 的儿子一定不能参加。

$d p_{x, 0} = \sum max (d p_{s o n [x], 0}, d p_{s o n [x], 1}) d p_{x, 1} = a_{x} + \sum d p_{s o n [x], 0}$
P2607 [ZJOI2008] 骑士

几乎和没有上司的舞会一样，只不过是在基环树上，我们只需要枚举断哪条边即可。不做赘述。

CF461B Appleman and Tree

定义 $d p_{x, 0 / 1}$ 表示以 $x$ 为根的的子树， $x$ 是否包含在一个有黑点的连通块中。

特征： $x$ 为根的子树答案可以由 $x$ 的儿子转移而来， $x$ 的儿子所在连通块是否有黑点决定了 $x$ 的方案数。

转移：

$x$ 所在连通块如果没有黑点，那么有黑点的子树必须跟 $x$ 联通，无黑点的子树也必须跟 $x$ 联通。

$x$ 所在连通块如果有黑点，那么有黑点的子树一定要跟 $x$ 断开，无黑点的子树必须要跟 $x$ 联通。

$d p_{x, 0} = d p_{x, 0} \times d p_{s o n [x], 0} + d p_{x, 0} \times d p_{s o n [x], 1} + d p_{x, 0} \times d p_{s o n [x], 1} d p_{x, 1} = d p_{x, 1} \times d p_{s o n [x], 0} + d p_{x, 1} \times d p_{s o n [x], 1} + d p_{x, 0} \times d p_{s o n [x], 1}$
P2585 [ZJOI2006]三色二叉树

$d p 1_{x, 0 / 1 / 2}$ 表示以 $x$ 为根的子树， $x$ 染成绿/红/蓝色时，有多少个点最多能被染成绿色。

$d p 2_{x, 0 / 1 / 2}$ 相应的表示最少有多少个点被染成绿色。

特征： $x$ 被染成什么颜色由 $x$ 的儿子和 $x$ 的兄弟决定，且与儿子个数有关。

转移：

这里以 $d p 1$ 的转移为例， $d p 2$ 完全可以类比。

当 $x$ 染绿色时， $x$ 的儿子只能染红色/蓝，若 $x$ 有一个儿子，则无所谓，反之它的两个儿子必须染不同的颜色。答案为儿子中答案的最大值 +1。

当 $x$ 不染绿色时， $x$ 的儿子只需要不与 $x$ 颜色相同，分别讨论 $x$ 为红/蓝的情况，分别讨论即可。答案为儿子中答案的最大值。

$x$ 无儿子时：

$d p_{x, 0} = d p_{x, 1} = d p_{x, 2} = 1$
$x$ 只有一个儿子时：

$d p_{x, 0} = max (d p_{s o n [x], 1}, d p_{s o n [x], 2}) + 1 d p_{x, 1} = max (d p_{s o n [x], 0}, d p_{s o n [x], 2}) d p_{x, 2} = max (d p_{s o n [x], 0}, d p_{s o n [x], 1})$
$x$ 有两个儿子时：

$d p_{x, 0} = max (d p_{l s o n [x], 1} + d p_{r s o n [x], 2}, d p_{l s o n [x], 2} + d p_{r s o n [x], 1}) + 1 d p_{x, 1} = max (d p_{l s o n [x], 0} + d p_{r s o n [x], 2}, d p_{l s o n [x], 2} + d p_{r s o n [x], 0}) d p_{x, 2} = max (d p_{l s o n [x], 0} + d p_{r s o n [x], 1}, d p_{l s o n [x], 1} + d p_{r s o n [x], 0})$
P4395 [BOI2003]Gem 气垫车

$d p_{x, i}$ 表示以 $x$ 为根的子树， $x$ 填 $i$ 时，总价值最小是多少。

发现 $d p_{x, i}$ 只能由 $d p_{s o n [x], j}$ 中满足 $i \neq j$ 且值最小的答案转移而来，而符合这两个条件的只会是 $d p_{s o n [x], j}$ 中的最大或次大值：当 $i$ 本来就不与最大值的 $j$ 相等时就是最大，反之是次大。

那么我们只需要定义另一个 $t p_{x, 0 / 1}$ 用来表示 $x$ 子树内 $d p$ 值的最大/次大值即可。同时记录一下满足 $d p_{x, i}$ 的 $d p$ 值中对应的最大值的 $i$ 是多少，记为 $m i_{x}$

转移：

$d p_{x, i} = \sum [m i_{x} \neq i] t p_{s o n [x], 0} + \sum [m i_{x} = i] t p_{s o n [x], 1}$
拓展：此类树形 DP 求树的直径。

我们用 $d p_{x, 0 / 1}$ 表示从 $x$ 出发的最长链/次长链。

然后 dfs，考虑每条边加进来之后是否会影响最大/次大值，直接转移即可。
和区间 DP 结合，以 $d p_{l, r}$ 表示树中 $[l, r]$ 的答案。

往往此类型的状态设计，类似区间 DP，会以区间的左右端点来描述状态，一个状态由比它更小的状态转移而来。

例：

P1040 加分二叉树

定义 $d p_{l, r}$ 表示树中区间 $[l, r]$ 加分最大值。

我们需要枚举对于当前区间 $[l, r]$ 作为一个子树时，哪个点作为根，以区间的左右端点 $[l, r]$ 分别为该子树内的节点下标最大和最小值，运用了同一子树内节点下标一定连续的这一特征，同时枚举根，也利用了区间 DP 枚举中间节点的套路。同时也启发我们，遇到二叉树三种遍历的题，可以考虑使用类似合并区间的方法，考虑对于一个区间而言它的答案是什么。

转移：

$d p_{l, r} = max (d p_{l, r}, d p_{l, k - 1} + d p_{k + 1, r} + d p_{k, k})$
换根 DP。用 $d p_{x}$ 表示整棵树以 $x$ 为根时的答案。

基于树形 DP 的基本模型，题目初始时不给出根节点，且我们需要知道每个点为根时的答案，暴力的做法是 $O (n^{2})$ 。换根 DP 可以将复杂度降低 $O (n)$ ，只需要两遍 dfs，第一遍以 1(或者任选一个节点)为根，在根节点切换时，直接通过一些已经计算过的数据在 $O (1)$ 就能得到另一个根的结果。

题目特征：需要选择一个点作为关键点/建立基站，问其它点到该关键点总的代价最大/最小是多少。

例：

P3478 [POI2008] STA-Station

首先以 $1$ 为根求出来所有的深度和。再定义 $d p_{x}$ 表示 $x$ 作为整棵树的根时，所有节点的深度和。

转移：

$d p_{x} = d p_{f a [x]} - s z_{x} + (s z_{1} - s z_{x})$
应该是换根 DP 的板子题了。

P2986 [USACO10MAR] Great Cow Gathering G

其实相当于求树的重心。我们也可以通过换根的方法来求。

定义 $d p_{x}$ 表示以 $x$ 作为整棵树的根时，所有奶牛要走的路程之和是多少。

第一遍 dfs 从 $1$ 开始求出当 $1$ 为根时的不方便程度。第二遍 dfs 以 $1$ 为基准求出其它点的不方便程度。

$f_{x}$ 用于第一遍 dfs 的转移， $d p_{x}$ 用于第二遍 dfs 的转移。

$f_{x} = \sum f_{s o n [x]} + s z_{s o n [x]} \times w (x, s o n [x]) d p_{x} = d p_{f a [x]} - d p_{x} \times w (x, f a [x]) + (s z_{1} - s z_{x}) \times w (x, f a [x])$
P3047 [USACO12FEB]Nearby Cows G

这道题我写了题解。就不在这里多赘述了。
树上背包。一般用 $d p_{x, i}$ 表示对于以 $x$ 为根的子树，选择了 $i$ 个点的答案。选择 $i$ 个点干什么一般要根据具体题意而定。答案就是问题，题目中要求什么这个 $d p$ 状态就表示什么。我们一般会枚举 $x$ 的子树中选了多少个点以及 $s o n [x]$ 选了多少个点，再按照背包的方式转移。

题目特征：一般而言，答案一般会与子树内选多少条边/多少个点有关，且 $d p_{x, i}$ 可以由 $d p_{y, j}$ 推出，转移类似于背包。

例：

P2015 二叉苹果树

定义 $d p_{x, i}$ 表示的是以 $x$ 为根的子树，有 $i$ 条边被保留时，最多能留住的苹果的数量。

我们可以枚举 $s o n [x]$ 子树中保留了多少条边，假设 $s o n [x]$ 子树中保留了 $j$ 条边， $x$ 子树中保留了 $i$ 条边，那么 $d p_{x, i}$ 就可以由 $d p_{x, i - j - 1}$ 和 $d p_{s o n [x], j}$ 转移而来，之所以要减一，是因为 $i \to j$ 这条边必须保留。

转移：

$d p_{x, i} = max (d p_{x, i}, d p_{x, i - j - 1} + d p_{s o n [x], j} + w (x, s o n [x]))$
P2014 [CTSC1997] 选课

定义 $d p_{x, i}$ 表示以 $x$ 为根的子树内，选择了 $i$ 门课程能获得的最大学分是多少。

可以枚举每一个 $s o n [x]$ 子树内选择了多少门课程，转移与上题类似，不做赘述。

转移：

$d p_{x, i} = max (d p_{x, i}, d p_{x, i - j} + d p_{s o n [x], j})$
P1270 “访问”美术馆

定义 $d p_{x, i}$ 表示走到节点 $x$ 时，剩余 $i$ 的时间，最多能拿到的画的数量。

由于此题模型是二叉树，所以我们只需要枚举分给左儿子的时间，那么分给右儿子的时间就是 $i$ 减去分给左儿子的时间。由于通过走廊还需要时间(即点有点权)，所以还需减去 $a_{x}$ 。

转移：

$d p_{x, i} = max (d p_{x, i}, d p_{l s o n [x], j} + d p_{r s o n [x], i - j - a [x]})$
P1273 有线电视网

定义 $d p_{x, i}$ 表示以 $x$ 为根的子树内，选了 $i$ 个用户的最大收益。

枚举 $s o n [x]$ 子树内选了多少个用户，然后考虑转移。最后同样要减去 $w (x, a [x])$ ，表示这条边的花费。

转移：

$d p_{x, i} = max (d p_{x, i}, d p_{x, i - j} + d p_{s o n [x], j} - w (x, a [x]))$
P3177 [HAOI2015] 树上染色

定义 $d p_{x, i}$ 表示以 $x$ 为根的子树，有 $i$ 个点染成了黑色的最大收益。

P4516 [JSOI2018] 潜入行动

这道题我写了题解。就不在这里多赘述了。
上述第二种和第四种相结合，同时需要记录 $x$ 选或者不选以及子树中选择多少个的问题特征。

一般定义 $d p_{x, i, 0 / 1}$ 表示 $x$ 为根的子树内，选择了 $i$ 个点/进行了 $i$ 次操作， $x$ 选/不选的答案。

P3698 [CQOI2017]小Q的棋盘

定义 $d p_{x, i, 0 / 1}$ 表示 $x$ 为根的子树内，走了 $i$ 步，是否回头的最多能经过的格点数量。

简要说明一下为什么要加最后一维。

如果我们直接定义 $d p_{x, i}$ 表示以 $x$ 为根的子树内走了 $i$ 步最多能经过的格点数量，那么有两种可能：
- 从 $x$ 的子树中绕几个圈圈后回到 $x$ ;
- 在 $x$ 的子树中绕几个圈圈后在向某一个子树一路走到死。
发现两种情况不能合并处理。所以我们要多记录一维是否回头(回头为 $1$ ，不回头为 $0$ )。

对于 $d p_{x, i, 1}$ ：由于到 $x$ 一定回头，所以 $s o n [x]$ 也必须回头，即只能从 $d p_{s o n [x], i, 1}$ 转移而来，转移类似于树上背包：

$d p_{x, i, 1} = max (d p_{x, i, 1}, d p_{x, i - j - 2, 1} + d p_{s o n [x], j, 1})$
之所以减去 $2$ 是因为来回要走两次 $x \to s o n [x]$ 这条边。

对于 $d p_{x, i, 0}$ ：发现对于 $s o n [x]$ 来说有三种可能：
- 在 $s o n [x]$ 之前就一路走到死；
- 在 $s o n [x]$ 处一路走到死；
- 在 $s o n [x]$ 之后一路走到死；
发现第三种情况会被前两种覆盖，所以我们只需要考虑前两种情况。

对于第一种情况，相当于要从上一个没有一路走到死的状态转移过来，即：

$d p_{x, i, 0} = max (d p_{x, i, 0}, d p_{x, i - j - 1, 1} + d p_{s o n [x], j, 0})$
因为只会走 $x \to s o n [x]$ 这条边一次所以只需要减 $1$ 。

对于第二种情况，相当于要从上一个已经一路走到死的状态转移过来，即：

$d p_{x, i, 0} = max (d p_{x, i, 0}, d p_{x, i - j - 2, 0} + d p_{s o n [x], j, 1})$
分别考虑转移即可。

后记

写于 NOIP2022 前。当我正在写这篇总结的时候，西安封城了，NOIP 大概率取消。那么是否非省队选手就直接无奖退役了呢，我不曾知晓，当然我大概率也是他们中的一员。

2022 年疫情因素众多，我们无法知晓未来发生的种种事情，也许会说”两年 OI 一场空，三天疫情见祖宗“，我起初也是这么觉得的，但现在突然就释然了，一切交给时间吧，做好我本来应该做好的事情就好了。

upd：陕西 NOIP2022 取消。

相关阅读:
js实现防抖函数,输入框持续输入打印最终的值
系统分屏后录音机向左右滑动报错问题
STC15单片机-看门狗介绍
【机器学习】红酒数据集和加利福尼亚的房价数据的随机森林算法详解
当mybatisPlus与tk.mybatis遇到更新
Java进阶篇--并发容器之ThreadLocal
【UI自动化】通过剪切板发送文本
在macOS上使用dosbox-x配置masm汇编环境
Linux 中的权限
5 张图告诉你 RocketMQ 为什么不使用 Zookeeper 做注册中心

原文地址：https://blog.csdn.net/m0_46222454/article/details/128037031