0x54 树形 DP

通过上一节的学习，读者应该对动态规划在树形结构上的实现方式有了初步的认识。给定一棵有 $N$ 个节点的树（通常是无根树，也就是有 $N - 1$ 条无向边），我们可以任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。在树上设计动态规划算法时，一般就以节点从深到浅（子树从小到大）的顺序作为DP的“阶段”。DP的状态表示中，第一维通常是节点编号（代表以该节点为根的子树）。大多数时候，我们采用递归的方式实现树形动态规划。对于每个节点 $x$ ，先递归在它的每个子节点上进行DP，在回溯时，从子节点向节点 $x$ 进行状态转移。

【例题】没有上司的舞会 TYVJ1052/CODEVS1380

Ural大学有 $N$ 名职员，编号为 $1 \sim N$ 。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 $H_{t}$ 给出，其中 $1 \leq i \leq N$ 。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

根据本节开始时的讨论，我们就以节点编号（子树的根）作为DP状态的第一维。因为一名职员是否愿意参加只跟他的直接上司是否参加有关，所以我们在每棵子树递归完成时，保留两个“代表信息”——根节点参加时整棵子树的最大快乐指数和，以及根节点不参加时整棵子树的最大快乐指数和，就可以满足“最优子结构”性质了。

设 $F[x,0]$ 表示从以 $x$ 为根的子树中邀请一部分职员参会，并且 $x$ 不参加舞会时，快乐指数总和的最大值。此时， $x$ 的子节点（直接下属）可以参会，也可以不参会。

设 $F[x,1]$ 表示从以 $x$ 为根的子树中邀请一部分职员参会，并且 $x$ 参加舞会时，快乐指数总和的最大值。此时， $x$ 的所有子节点（直接下属）都不能参会。

其中， $Son(x)$ 表示 $x$ 的子节点集合。

本题输入的是一棵有根树（指定了节点间的上下属关系），故我们需要先找出没有上司的节点 root 作为根，DP 的目标为 $\max(F[root, 0], F[root, 1])$ 。时间复杂度 $O(N)$ 。

vector son[10010];
int f[10010][2], v[10010], h[10010], n;

void dp(int x) {
    f[x][0] = 0;
    f[x][1] = h[x];
    for (int i = 0; i < son[x].size(); i++) {
        int y = son[x][i];
        dp(y);
        f[x][0] += max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}

正如深度优先和广度优先都可以对树或图进行遍历一样，除了自顶向下的递归外，我们也可以用自底向上的拓扑排序来执行树形DP。通常前者已经足够，这里我们就不再赘述。

在更多的题目中，树是以一张 $N$ 个点、 $N - 1$ 条边的无向图的形式给出的。在这种情况下使用树形DP算法时，我们就要用邻接表存下来这 $N - 1$ 条无向边，任选一个点出发执行深度优先遍历，并注意标记节点是否已经被访问过，以避免在遍历中沿着反向边回到父节点。

$\spadesuit$ 背包类树形DP

【例题】选课 TYVJ1051

学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了 $N(N \leq 300)$ 门的选修课程，每个学生可选课程的数量 $M$ 是给定的。学生选修了这 $M$ 门课并考核通过就能获得相应的学分。

在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。例如《Windows 程序设计》必须在选修了《Windows 操作基础》之后才能选修。我们称《Windows 操作基础》是《Windows 程序设计》的先修课。每门课的直接先修课最多只有一门。两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。假定课程之间不存在时间上的冲突。

因为每门课的先修课最多只有一门（对应着树中每个节点至多只有1个父亲），所以这 $N$ 门课程构成了森林结构（若干棵树，因为可能有不止一门课没有先修课）。简便起见，我们可以新建一个“虚拟课程”——0号节点，作为“实际上没有先修课的课程”的先修课，把包含 $N$ 个节点的森林转化为包含 $N + 1$ 个节点的树，其中节点0为根节点。

设 $F[x,t]$ 表示在以 $x$ 为根的子树中选 $t$ 门课能够获得的最高学分，设 $x$ 的子节点集合为 $\operatorname{Son}(x)$ ，子节点个数 $p = |\operatorname{Son}(x)|$ 。修完 $x$ 这门课后，对于 $x$ 的每个子节点 $y_i \in \operatorname{Son}(x)$ ，我们可以在以 $y_i$ 为根的子树中选修若干门课（记为 $c_i$ ），在满足 $\sum c_i = t - 1$ 的基础上获得尽量多的学分。

当 $t = 0$ 时，显然 $F[x,t] = 0$ 。当 $t > 0$ 时，根据以上分析，状态转移方程如下：

该方程其实是一个分组背包模型。有 $p = |\operatorname{Son}(x)|$ 组物品，每组物品都有 $t - 1$ 个，其中第 $i$ 组的第 $j$ 个物品的体积为 $j$ ，价值为 $F[y_i, j]$ ，背包的总容积为 $t - 1$ 。我们要从每组中选出不超过 1 个物品（每个子节点 $y$ 只能选一个状态转移到 $x$ ），使得物品体积不超过 $t - 1$ 的前提下（在修完 $x$ 后，还能选修 $t - 1$ 门课），物品价值总和最大（获得最多学分）。当然， $x = 0$ 是一个特例，因为虚拟的根节点实际上不需要被选修，此时背包总容积应为 $t$ 。我们用分组背包进行树形 DP 的状态转移，关键部分的代码如下：

for (int i = 0; i < son[x].size(); i++) { // 循环子节点（物品）  
    int y = son[x][i];  
    dp(y);  
    // 倒序循环当前选课总门数（当前背包体积）  
    for (int t = m; t >= 0; t--)  
        // 循环更深子树上的选课门数（组内物品）  
        // 此处使用倒序是为了正确处理组内体积为 0 的物品  
        for (int j = t; j >= 0; j--)  
            if (t - j >= 0)  
                f[x][t] = max(f[x][t], f[x][t - j] + f[y][j]);  
    }  
    if (x != 0) // x 不为 0 时，选修 x 本身需要占用 1 门课，获得相应学分  
        for (int t = m; t > 0; t--)  
            f[x][t] = f[x][t - 1] + score[x];

这类题目被称为背包类树形DP，又称有树形依赖的背包问题。它实际上是背包与树形DP的结合。除了以“节点编号”作为树形DP的阶段，通常我们也像线性DP一样，把当前背包的“体积”作为第二维状态。在状态转移时，我们要处理的实际上就是一个分组背包问题。

值得一提的是，这类题目还可以先按照一个被称为“左儿子右兄弟”的方法，把多叉树转化成二叉树，再进行计算。这样一来，在状态转移时就只需要枚举左右两棵子树中的一棵选了多少门课。不过，这种方法需要做额外的转换，在复杂的题目中很容易把节点之间的父子关系、兄弟关系混淆，容易出错。因此，本书提倡读者直接在原始的多叉树上使用分组背包模型进行背包类树形DP。

二次扫描与换根法

【例题】Accumulation Degree POJ3585

有一个树形的水系，由 $N - 1$ 条河道和 $N$ 个交叉点组成。我们可以把交叉点看作树中的节点，编号为 $1 \sim N$ ，河道则看作树中的无向边。每条河道都有一个容量，连接 $x$ 与 $y$ 的河道的容量记为 $c(x, y)$ 。河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。除了源点之外，树中所有度数为1的节点都是入海口，可以吸收无限多的水，我们称之为汇点。也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。整个水系的流量就定义为源点单位时间发出的水量。

在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。 $N \leq 2 * 10^{5}$ 。

本题是一个“不定根”的树形DP问题。这类题目的特点是，给定一个树形结构，需要以每个节点为根进行一系列统计。我们一般通过两次扫描来求解此类题目：

1. 第一次扫描时，任选一个点为根，在“有根树”上执行一次树形DP，也就是在回溯时发生的、自底向上的状态转移。

2. 第二次扫描时，从刚才选出的根出发，对整棵树执行一次深度优先遍历，在每次递归前进行自顶向下的推导，计算出“换根”后的解。

本书以“二次扫描与换根法”来指明与上述过程类似的算法。

我们先来考虑本题的朴素解法——枚举源点 $s$ ，然后计算水系流量。把源点作为树根，整个水系就变成了一棵有根树，每条河道的方向也可以直接得出，如下图所示：

无根树(n个点、n-1条边的无向连通图)

有根树

因此，以树根为源点时，每个节点都只会从父节点获得水源，并流向它的子节点。每个节点的“流域”就是以该点为根的子树。这非常符合树形DP的应用场景——每棵子树都是一个“子问题”。

设 $D_{s}[x]$ 表示在以 $x$ 为根的子树中，把 $x$ 作为源点，从 $x$ 出发流向子树的流量最大是多少。

对于枚举的每个源点 $s$ ，可以用树形DP在 $\mathrm{O}(N)$ 的时间内求出 $D_{s}$ 数组，并用 $D_{s}[s]$ 更新答案。所以，最终的时间复杂度为 $\mathsf{O}(N^2)$ 。下面的代码给出了一次树形DP的过程。在主函数中调用dp(s)，完成后 $d[s]$ 就是所求的 $D_{s}[s]$ 。

void dp(int x) {
    v[x] = 1; // 访问标记
    d[x] = 0;
    for (int i = head[x]; i; i = Next[i]) { // 邻接表存储
        int y = ver[i];
        if (v[y].continue;
            dp(y);
            if (deg[y] == 1) d[x] += edge[i]; // edge[i]保存 c(x,y)
                else d[x] += min(d[y], edge[i]);
    }
}

用“二次扫描与换根法”代替源点的枚举，可以在 $O(N)$ 的时间内解决整个问题。首先，我们任选一个源点作为根节点，记为 root，然后采用上面的代码进行一次树形 DP，求出 $D_{root}$ 数组，简记为 $D$ 数组。

设 $F[x]$ 表示把 $x$ 作为源点，流向整个水系，流量最大是多少。对于根节点 root，显然有 $F[root] = D[root]$ 。

假设 $F[x]$ 已被正确求出，考虑其子节点 $y, F[y]$ 尚未被计算。 $F[y]$ 包含两部分：

1. 从 $y$ 流向以 $y$ 为根的子树的流量，已经计算并保存在 $D[y]$ 中。

2. 从 $y$ 沿着到父节点 $x$ 的河道，进而流向水系中其他部分的流量。

以3为根

以1为根

以2为根

因为把 $x$ 作为源点的总流量为 $F[x]$ ，从 $x$ 流向 $y$ 的流量为 $\min(D[y], c(x, y))$ ，所以从 $x$ 流向除 $y$ 以外其他部分的流量就是二者之差。于是，把 $y$ 作为源点，先流到 $x$ ，再流向其他部分的流量就是把这个“差”再与 $c(x, y)$ 取最小值后的结果。

当然，对于度数为1的节点 $x$ ，需要进行特殊判断。

$F[y]$ 就是把源点（树根）从 $x$ 换成 $y$ 后，流量的计算结果。这是一个自顶向下的递推方程，我们通过一次深度优先遍历即可实现。

void dfs(int x) {  
    v[x] = 1;  
    for (int i = head[x]; i; i = Next[i]) {  
        int y = ver[i];  
        if (v[y]) continue;  
        if (deg[x] == 1) f[y] = d[y] + edge[i];  
        else f[y] = d[y] + min(f[x] - min(d[y], edge[i]), edge[i]);  
        dfs(y);  
    }  
}  
// 主函数中的调用  
int root = 1;  
dp(root);  
memset(v, 0, sizeof(v));  
f[root] = d[root];  
dfs(root);  
int ans = 0;  
for (int i = 1; i <= n; i++)  
    ans = max(ans, f[i]);  
cout << ans << endl;

$0 \times 55$ 环形与后效性处理

$\spadesuit$ 环形结构上的动态规划问题

在许多环形结构的问题中，我们都能够通过枚举法，选择一个位置把环断开，变成线性结构进行计算，最后根据每次枚举的结果求出答案。我们把能通过上述枚举方式求解的环形问题称为“可拆解的环形问题”，这也是本节的主要研究对象。我们的目标是采取适当的策略避免枚举，从而使时间复杂度得到降低。

【例题】Naptime POJ2228/TYVJ1963

在某个星球上，一天由 $N$ 个小时构成，我们称0点到1点为第1个小时、1点到2点为第2个小时，依此类推。在第 $i$ 个小时睡觉能够恢复 $U_{i}$ 点体力。在这个星球上住着一头牛，它每天要休息 $B$ 个小时。它休息的这 $B$ 个小时不一定连续，可以分成

若干段，但是在每段的第一个小时，它需要从清醒逐渐入睡，不能恢复体力，从下一个小时开始才能睡着。

为了身体健康, 这头牛希望遵循生物钟, 每天采用相同的睡觉计划。另外, 因为时间是连续的, 即每一天的第 $N$ 个小时和下一天的第 1 个小时是相连的 ( $N$ 点等于 0 点), 这头牛只需要在每 $N$ 个小时内休息够 $B$ 个小时就可以了 (就像地球上的人类, 如果每天需要休息 9 个小时, 那么可以 23 点入睡、6 点起床, 13 点午睡、15 点起床, 这样能够恢复体力的时间就是从 06 点和 1415 点, 共 7 个小时)。

请你帮忙给这头牛安排一个睡觉计划，使它每天恢复的体力最多。 $1 \leq N \leq 3830$ 。

先来考虑一个简化的问题。假设第 $N$ 个小时和下一天的第1个小时不是相连的，这样星球上每天的时间就是线性的，从第1个小时开始，到第 $N$ 个小时结束，可以用一个长度为 $N$ 的序列 $\{U_i\}$ 来描述一天内每小时的体力恢复情况。我们从这个序列中选出 $B$ 项，按照题目中的计算方法，让一天里恢复的体力尽量多。利用前面几节学到的线性DP的知识，容易设计出状态表示和转移方程。

设 $F[i,j,1]$ 表示前 $i$ 个小时休息了 $j$ 个小时，并且第 $i$ 个小时正在休息，累计恢复的体力的最大值。 $F[i,j,0]$ 表示前 $i$ 个小时休息了 $j$ 个小时，并且第 $i$ 个小时没有在休息，累计恢复的体力的最大值。

在这个简化的问题中，第1个小时一定是每天的开始，不可能处于熟睡状态。因此DP的初值为 $F[1,0,0] = 0$ ， $F[1,1,1] = 0$ ，其余均为负无穷。

目标为：max(F[N,B,0],F[N,B,1])。

到目前为止，我们解决的“线性问题”仅比原来的“环形问题”少了一种情况，即在第1个小时熟睡，并获得 $U_{1}$ 点体力。如果在原问题的最优解中，第 $N$ 个小时与第1个小时不都在休息，那么上面简化问题的答案即为所求。为了补充这个缺少的情况，可以强制令第 $N$ 个小时和第1个小时都在休息，使第1个小时能够恢复体力。我们仍然采用上述线性DP的方法，只需把初值和目标修改为：

初值： $F[1,1,1] = U_{1}$ ，其余均为负无穷。

目标： $F[N,B,1]$

两次动态规划结果中的较优者就是原问题的答案。

本题的解法本质上是把问题拆成了两部分。第一部分不可能在第 1 小时恢复体力 $U_{1}$ , 而第二部分强制在第 1 小时获得 $U_{1}$ 点体力。这两部分合起来能够覆盖整个问题。无论是哪一部分, 因为第 $N$ 小时和第 1 小时之间的特殊关系被确定, 所以我们就能把环拆开, 用线性 DP 计算。这就是我们要介绍的第一种策略——执行两次 DP, 第一次

在任意位置把环断开成链，按照线性问题求解；第二次通过适当的条件和赋值，保证计算出的状态等价于把断开的位置强制相连。

我们要介绍的第二种策略是在任意位置把环断开成链，然后复制一倍接在末尾。0x53节“区间DP”中探讨过一道这样的例题，请读者回顾。下面再给出一道采用本策略的例题。

【例题】环路运输

在一条环形公路旁均匀地分布着 $N$ 座仓库，编号为 $1 \sim N$ ，编号为 $i$ 的仓库与编号为 $j$ 的仓库之间的距离定义为 $\text{dist}(i, j) = \min(|i - j|, N - |i - j|)$ ，也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。每座仓库都存有货物，其中编号为 $i$ 的仓库库存量为 $A_i$ 。在 $i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $A_i + A_j + \text{dist}(i, j)$ 。求在哪两座仓库之间运送货物需要的代价最大。 $1 \leq N \leq 10^6$ 。

我们在任意位置（例如仓库1和 $N$ 之间）把环断开，复制一倍接在末尾，形成长度为 $2N$ 的直线公路。在转化之后的模型中，公路旁均匀分布着 $2N$ 座仓库，其中 $A_{i} = A_{i + N}$ $(1\leq i\leq N)$ 。

对于原来环形公路上的任意两座仓库 $i$ 和 $j (1 \leq j < i \leq N)$ ，如果 $i - j \leq N / 2$ ，那么在新的直线公路上，仍然可以对应成在 $i$ 和 $j$ 之间运送货物，代价为 $A_i + A_j + i - j$ 。

如果 $i - j > N / 2$ ，那么可以对应成在 $i$ 和 $j + N$ 之间运送货物，代价为 $A_{i} + A_{j + N} + j + N - i$ ，其中 $j + N - i = N - (i - j) \leq N / 2$ 。

综上所述，原问题可以等价转化为：长度为 $2N$ 的直线公路上，在满足 $1 \leq j < i \leq 2N$ 并且 $i - j \leq N / 2$ 的哪两座仓库 $i$ 和 $j$ 之间运送货物，运送代价 $A_{i} + A_{j} + i - j$ 最大？

我们可以枚举 $i$ ，对于每个 $i$ ，需要找到一个 $j \in [i - N / 2, i - 1]$ ，使 $A_{j} - j$ 尽量大。在0x12节的“最大子序和”这道例题的解答中，我们已经探讨过同样的问题。使用单调队列进行维护，可以在均摊O(1）的时间内找到这样的 $j$ 。整个算法的时间复杂度为 $O(N)$ 。

$\spadesuit$ 有后效性的状态转移方程

从最初学习DP开始，我们就多次强调，“阶段”是动态规划的三要素之一，“无后效性”是应用动态规划算法的三前提之一。事实上，在一些题目中，当我们根据题目的关键点抽象出“状态维度”，并设计出状态表示和状态转移方程后，却发现这道形似DP的题目不满足“无后效性”这一基本条件——部分状态之间互相转移、互相影响，

构成了环形，无法确定出一个合适的DP“阶段”，从而沿着某个方向执行递推。

事实上，我们可以把动态规划的各状态看作未知量，状态的转移看作若干个方程。如果仅仅是“无后效性”这一条前提不能满足，并且状态转移方程都是一次方程，那么我们可以不进行线性递推，而是用高斯消元直接求出状态转移方程的解。

在更多的题目中，动态规划的状态转移“分阶段带环”——我们需要把DP和高斯消元相结合，在整体层面采用动态规划框架，而在局部使用高斯消元解出互相影响的状态。我们用一道例题来具体说明这类情况。

*【例题】Broken RobotCodeforces24D

给定一张 $N * M$ 的棋盘，有一个机器人处于 $(x, y)$ 位置。这个机器人可以进行很多轮行动，每次等概率地随机选择停在原地、向左移动一格、向右移动一格或向下移动一格。当然机器人不能移出棋盘。求机器人从起点走到最后一行的任意一个位置上，所需行动次数的数学期望值。 $1 \leq N, M \leq 1000$ 。

在0x51节“线性DP”的“传纸条”一题中，因为只能往右和往下传递，所以DP状态在行、列两个维度上都构成线性增长的形式。最后我们以传递的步数作为DP的阶段。在本题中，我们容易想到，设 $F[i,j]$ 表示机器人从位置 $(i,j)$ 走到最后一行，所需行动次数的期望值。

机器人在第1列时不能再向左走， $F[i,1] = \frac{1}{3} (F[i,1] + F[i,2] + F[i + 1,1]) + 1.$

同理，在第 $M$ 列时， $F[i, M] = \frac{1}{3} (F[i, M] + F[i, M - 1] + F[i + 1, M]) + 1$ 。

当 $2 \leq j \leq M - 1$ 时， $F[i,j] = \frac{1}{4} (F[i,j] + F[i,j - 1] + F[i,j + 1] + F[i + 1,j]) + 1$ 。

初值： $\forall j\in [1,M],F[N,j] = 0$ 。目标： $F[x,y]$

观察上面的状态转移方程，我们发现，因为第 $i$ 行的状态只能转移到第 $i + 1$ 行，所以“行”维度仍然满足“无后效性”。但是在同一行内，机器人既能向左走，也能向右走，甚至可以原地不动，各状态之间互相转移，无法确定一个递推顺序。故我们采用DP套高斯消元的算法来求解本题。

我们先以行号为阶段，从 $M$ 到 $x$ 倒序扫描每一行，依次计算以该行的每个位置为起点走到最后一行，所需行动次数的数学期望值。

接下来我们考虑每行内的计算方法。在计算第 $i$ 行的状态时，因为第 $i + 1$ 行的状态已经计算完毕，我们可以把 $F[i + 1, j]$ 看作已知数。于是，状态转移方程中就只剩下 $F[i, 1], F[i, 2], \dots, F[i, M]$ 这 $M$ 个未知量。第 $i$ 行的每个位置可以列出一个方程，共 $M$ 个方程。因此，我们可以用高斯消元解出 $F[i, 1], F[i, 2], \dots, F[i, M]$ 的值。

列出上述 $M$ 个方程，移项并仔细观察，可以发现高斯消元的系数矩阵除主对角线和对角线两侧的斜线之外，其余部分均为0。下面就是一个 $M = 5$ 时的系数矩阵。

在这样的矩阵中执行高斯消元，在每一行中实际上只有2~3个位置需要相减，只需 $O(M)$ 的时间即可求出各个未知量的解。整个算法的时间复杂度为 $O(NM)$ 。注意 $M = 1$ 时，上述DP算法有边界问题，需要进行特判。

值得一提的是，为什么我们用 $F[i,j]$ 表示从 $(i,j)$ 走到最后一行的期望步数，按行号倒序进行递推，而不是用 $F[i,j]$ 表示 $(x,y)$ 到 $(i,j)$ 的期望步数，并正序递推？原因是，根据数学期望的定义，若正序递推，则还需求出 $(x,y)$ 到最后一行每个位置的概率 $p[N,j]$ ，计算 $\sum_{j=1}^{M} p[N,j] * F[N,j]$ 才能得到答案，较为复杂。事实上，很多数学期望DP都会采取倒推的方式执行，请读者留心思考。

通过本章前五节的学习，读者应该对动态规划的本质、动态规划的设计与实现方法有了更加深刻的认识。读者应能在线性（包括背包、区间）、树形等各种结构上初步判断DP是否适用，解释DP的思想，并熟练使用DP算法求解不太困难的问题。遇到简单的环形问题和后效性问题，读者也应该能从容应对。

从下一节开始，我们将把重点放在动态规划的优化上。大部分情况下，我们会直接给出DP状态表示与转移方程，切入DP优化的正题，不再花费过多篇幅解释设计思路。因此，请读者根据自身水平，尽量完成0x5E节的第2~16题，务必把所学知识巩固扎实。