树形 DP 讲课笔记
zxh_qwq
·
·
算法·理论
题单：https://www.luogu.com.cn/training/1034084
::::info[P3621 [APIO2007] 风铃]
:::success[Hint 1 (6 min)]
考虑一个无解情况。
若一个子树的左右子树均有深浅两种情况，则其无解。
:::
:::success[Solution (15 min)]
考察知识点：DFS 求解树形 DP。
不难发现，若所有叶子均一样深则输出 0。
若叶子深度的差 \geq 2 则一定无解，输出 -1。
若一个子树的左右子树均有深浅两种情况，则无解，输出 -1。
剩下的情况就好处理了。
考虑什么时候需要交换。
若左子树全为深，且右子树有深有浅，则一定交换。
若左子树有深有浅，且右子树全为浅，则一定交换。
否则一定不交换。
利用树形 DP 或 DFS 统计子树内的深浅叶子节点个数。
可以试着自行写代码。(15 min)
:::
::::
::::info[P2610 [ZJOI2012] 旅游]
:::success[Hint 1 (7 min)]
考虑建图。一步能到达的两个城市间建边。
:::
:::success[Hint 2 (11 min)]
发现图中恰有 n-3 条边，n-2 个城市。
于是这是一棵树。
:::
:::success[Hint 3 (14 min)]
任意一条树的路径都可以被一条直线段覆盖。
自行证明。
:::
:::success[Solution (18 min)]
考察知识点：DFS 求解树形 DP。
结合 Hint 1,2,3 的结论，我们相当于求出这棵树的直径长度。
求直径可以 DP，DFS 等。
建图过程使用 map 维护，若两个城市间存在一条共边则可以一步到达。
可以试着自行写代码。(20 min)
:::
::::
::::info[P16189 [COI 2018] Paprike 胡椒]
:::success[Hint 1 (8 min)]
考虑设一个 sum_u 表示最小刀数时 u 所在的联通块的最小值。
显然每次选取子树的时候，选的 sum_u 越多越好，贪心转移。
:::
:::success[Solution (13 min)]
考察知识点：贪心优化树形 DP。
设 dp_u 以 u 为根的子树中所有花环辣度小于等于 k 时，切的最小刀数。
对子节点按 $sum$ 排序，一直取最小的直到再取超过 $k$。
剩下的都切一刀即可。
可以试着自行写代码。(15 min)
:::
::::
::::info[[P13680 [IAMOI R2] 未送出的花](https://www.luogu.com.cn/problem/P13680)]
:::success[Hint 1 (8 min)]
整棵树盛开度的最优形态一定是一个大根堆。
那么我们可以知道，一个点 $u$ 的美丽值就是根到它的路径上第 $\lceil\frac{dep_u}{2}\rceil$ 个点的盛开度，$dep_u$ 表示深度。
:::
:::success[Hint 2 (14 min)]
对于每个点，我们可以 DP 求出它被作为美丽值的次数。
:::
:::success[Hint 3 (20 min)]
考虑求 $k$ 朵花的时候。
按照盛开度从大到小枚举所有的点，并且累加 $cnt$，直到 $cnt \ge k$ 的时候结束，答案就是最后一个点的盛开度。
观察上述过程，不难发现盛开度从大到小排序后，一段前缀盛开度对应的点构成一个包含 $1$ 号点的联通块。
:::
:::success[Hint 4 (29 min)]
可以转化为对于 $k\in[1,n]$，求一个包含 $1$ 号点的连通块，满足这个连通块的 $\sum cnt_i\ge k$，同时点数最少。
这个等价于求包含 $1$ 号点的，大小为 $1,2,\cdots,n$ 的联通块的 $cnt$ 之和最大能到多少。
这是可以树形 DP 的，如果要构成一个联通块，那么如果我们不选点 $u$ 那么 $u$ 的子树中的点都不能选。
一个有限制的背包问题。
考虑 DFS 序。
:::
:::success[Solution (40 min)]
考察知识点：贪心优化树形 DP。
考虑拍到 DFS 序上，再把整个 DFS 序列翻转过来，那么第 $i$ 个点的子树区间就是 $[i-siz_{id_i}+1,i]$，其中 $id_i=j$ 表示 DFS 序为 $i$ 的点是 $j$，$siz$ 表示子树大小。
那么设 $dp_{i,j}$ 表示枚举到第 $i$ 个点，选了 $j$ 个，$cnt$ 之和的最大值。
- 如果选 $i$，那么 $dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-1}+cnt_{id_i})$。
- 否则 $dp_{i,j}=\max(dp_{i,j},dp_{i-siz_{id_i},j})$。
就做完了。
可以先不用写代码。
:::
::::
---
::::info[[P12136 [蓝桥杯 2025 省 B] 生产车间](https://www.luogu.com.cn/problem/P12136)]
:::success[Hint 1 (5 min)]
每个节点有容量限制，转化成背包的形式。
:::
:::success[Hint 2 (11 min)]
考虑树形 DP，由于每个节点提供的值不是越多越好，需要进行分组背包。
:::
:::success[Solution (18 min)]
设 $dp_{i,j}$ 表示节点 $i$ 的权值能否恰好达到 $j$，初始叶节点只有 $dp_{u,w_u}$ 为真，其他节点 $dp_{u,0}$ 为真。
从下往上进行 DP，对于非叶节点 $u$，枚举 $u$ 的儿子 $v$，对于每个 $i,j(i+j\le w_u,j\le w_v)$，若 $dp_{v,j}$ 为真且 $dp_{u,i}$ 为真，则 $dp_{u,i+j}$ 为真。
输出节点 $1$ 最大能达到的权值即可。
可以试着自行写一下。(20 min)
:::
::::
::::info[[P14150 不动鸣神，恒常乐土](https://www.luogu.com.cn/problem/P14150)]
:::success[Hint 1 (2 min)]
图是森林。
:::
:::success[Hint 2 (8 min)]
注意到 $k \le 10$，考虑放进 DP 状态。
:::
:::success[Hint 3 (20 min)]
直接设 $f_{i,j}$ 表示没选第 $i$ 个节点而选了 $j$ 个儿子的答案，$g_i$ 表示选了第 $i$ 个节点的答案。
$g_i$ 转移是朴素的。考虑 $f_{i,j}$ 的转移。
一定是按某个式子的大小排序后选点。
:::
:::success[Solution (35 min)]
考察知识点：贪心优化树形 DP / 树上背包。
朴素做法：
- 首先选了自己的答案直接从下面没选的答案里更新，有 $g_i=a_i+\displaystyle\sum_{v\in son(i)}\max_{j\in[0,k-1]}f_{v,j}$。
- 然后考虑没选自己的答案：
- 首先儿子也没选的答案和选了自己的答案的更新方式类似，直接从下面没选的答案里更新，有 $g_i=a_i+\displaystyle\sum_{v\in son(i)}\max_{j\in[0,k]}f_{v,j}
-
然后选了 1 个儿子的答案其实就是从一个没选的里面选一个，减去不选它的贡献，加上选它的贡献，即 f_{i,1}=\displaystyle\max_{v\in son(i)}\left(f_{i,0}-\max_{j\in[0,k]}f_{v,j}+g_v\right)。
-
然后选了 2 个儿子的答案不能再用这个方程了，因为 \displaystyle\max_{v\in son(i)}\left(f_{i,1}-\max_{j\in[0,k]}f_{v,j}+g_v\right) 中由于 f_{i,1} 固定，所以选出来的 v 其实是固定的。但这也就意味着我们肯定是按一定的顺序选这些点，顺序就是 -\max_{j\in[0,k]}f_{v,j}+g_v 降序排序，然后直接转移即可。
- 最终答案是 \max\left\{\displaystyle\max_{i\in[0,k]}f_{rt,i},g_{rt}\right\}。
树上背包做法：
考虑分当前儿子选不选，选就加上 f_{v,k-1}，不选就加上 f_{v,k}。
然后树上背包即可。
对每棵树分别计算答案然后加起来。
可以先不用写代码。
:::
::::
::::info[P2515 [HAOI2010] 软件安装]
:::success[Hint 1 (6 min)]
发现图是一个基环树。中间的点环状依赖，要么都选要么都不选，可以缩点。
:::
:::success[Hint 2 (15 min)]
考虑建树，建一个超级原点 0 连接所有没有依赖的点。
然后树形 DP。
:::
:::success[Solution (25 min)]
考察知识点：缩点，树上背包。
考虑树上背包。
设 f_{i,j} 表示 i 的子树内用不超过 j 的空间的最大价值。
DP 转移是朴素的。
可以先不用写代码。
:::
::::
::::info[P11501 [ROIR 2019] 探险队 (Day 2) & P2607 [ZJOI2008] 骑士]
:::success[Hint 1 (5 min)]
发现这是一棵基环树，考虑分开环与树 DP。
:::
:::success[Hint 2 (8 min)]
对于每个环上的点，考虑其子树的最大贡献。
在子树内 DP。
:::
:::success[Hint 3 (12 min)]
考虑只有环，每个点带权怎么做。
:::
:::success[Solution (18 min)]
考察知识点：基环树 DP（树形 DP + 环形 DP）。
对每个子树 DP。
设 f_{u,0} 表示不选这个点的最大答案，f_{u,1} 表示选了这个点。
朴素 DP 转移到环上。
环上的 DP 也是朴素的。
可以先不用写代码。
:::
::::
::::info[P3478 [POI 2008] STA-Station]
:::success[Hint 1 (8 min)]
设 dp_u 表示当点 u 作为根时的深度之和。
考虑当根从一个点变成它的儿子时其他节点的深度如何变化。
:::
:::success[Solution (15 min)]
考察知识点：换根 DP。
当根从 u 变为 u 的子节点 v 时，考虑答案发生的变化。
不难发现，发现在儿子的子树外的点深度会增加 1，子树内的点深度会减 1。
那么就有 dp_v=dp_u+(n-siz_v)-siz_v。
其中 siz_x 是 x 的子树大小。
先钦定节点 1 为根，求出 dp_1 和每个节点的 siz，然后换根转移即可。
可以试着自行写一下。(15 min)
:::
::::
::::info[P6554 Promises I Can't Keep]
:::success[Hint 1 (4 min)]
注意是等概率流向叶子不是等概率流向儿子。
:::
:::success[Hint 2 (14 min)]
发现可以变成根到每个叶子路径权和除以叶子数量，如果当前根是叶子需要额外减 1。
:::
:::success[Hint 3 (25 min)]
考虑换根 DP，以 1 为根的答案是容易求的，只需要处理每个点子树内叶子个数，乘上点权加和，同时对叶子打标记。
:::
:::success[Solution (35 min)]
考察知识点：换根 DP。
转移时，设当前节点为 v，父亲为 u，若 v 不是叶子，f_v=f_u-cnt_v \times a_u+(cnt_1-cnt_v) \times a_v，其中 cnt 是叶子个数，a 是点权。如果是，f_v=f_u-a_u+(siz_1-1)\times a_v-a_v。
可以试着自行写一下。(20 min)
:::
::::
::::info[P2458 [SDOI2006] 保安站岗]
:::success[Hint 1 (8 min)]
考虑在 DP 里维护这个点被覆盖的状态。
由父亲，儿子，自身覆盖有三种情况。
:::
:::success[Solution (13 min)]
设 dp_{u,0/1/2} 表示 u 节点被覆盖的状态。
设 v 为 u 的一个子节点，考虑转移。
$dp_{u,1}=\sum \min(dp_{v,1},dp_{v,2})+ \min({dp_{v,2}})$。
$dp_{u,2}=\sum \min(dp_{v,0},dp_{v,1},dp_{v,2}) + r_u$。
可以试着自行写代码。(15 min)
:::
::::
::::info[[P3047 [USACO12FEB] Nearby Cows G](https://www.luogu.com.cn/problem/P3047)]
:::success[Hint 1 (10 min)]
分开考虑一个节点 经过其父亲 / 不经过其父亲 距离为 $k$ 的点。
:::
:::success[Solution (25 min)]
设 $f_{u,k}$ 表示在 $u$ 子树内离节点 $u$ 距离恰好是 $k$ 的点的个数，$g_{u,k}$ 是总个数。
$f$ 的求解是朴素的。通过 $f$ 推 $g$，$g_{v,k}$ 加上 $g_{u,k-1} - f_{v,k-2}$ 来容斥，其中 $u$ 是 $v$ 的父节点。
可以试着自行写一下。(15 min)
::::