2023 国庆集训 Day 3B 笔记
更佳的阅读体验：2023 国庆集训 Day 3B 笔记，本文同步发表于 洛谷博客。
以下内容为个人总结，如有错误或您有不同见解，欢迎指出。
树形 DP
- 依照树的性质进行的 DP。
- 把树分为许多子结构，通过子结构包含的信息来设计状态，通常是由子结点向父节点转移。
- 以下所有关于树形 DP 的内容，规定
x 为当前结点，y 为其子节点。
求树上两两距离和
- 求
dis[i][j] 。 - 统计每条边的贡献：
size[x] \times (n - size[x]) 。
洛谷 P3047 - Nearby Cows G
- 令
f[x][i] 为x 子树内，和x 距离\le i 的点的点权和，f[x][i] = c_x + \sum f[y][i - 1] 。 - 求
ans_x 时，令fa[x][i] 为x 的第i 级祖先，则ans_x = \sum f[fa[x][i]][k - i] - f[fa[x][i - 1]][k - i - 1] 。 - 复杂度为
O(nk) 。
洛谷 P2014 - 选课
- 把
a 是b 的先修课程视为a 是b 的父亲，那么会形成一个森林。 - 设
f[x][i] 为x 子树中修读i 门课的最大学分数。 - 依次枚举
x 的每个儿子，设当前儿子为y ，利用老f[x] 与f[y] 合并出新f[x] 。老f[x] 意为不含y 子树的信息（也就是只考虑y 之前的所有儿子的子树）。 - 那么
f_新[x][i] = \max(f_老[x][j] + f[y][i - j]) 。注意由于根节点x 必须选，那么要求j > 0 。 - 复杂度为
O(nm^2) 。 - 经典的树形背包问题，利用 DFS 序可以优化为
O(nm) 。
求树的直径
- 类似于上一题的合并，记录
x 的当前深度。 - 如果要对直径计数，额外记录数量。
洛谷 P3174 - 毛毛虫
- 答案为
\max (\sum (deg[i] - 1) + 2) ，树形 DP 求最长链。 - 或使用两遍 DFS 求直径。
树上最大独立集 / 最小点覆盖
- 最大独立集：选择尽可能多的点，但是父亲和儿子不能同时选择； 最小点覆盖：选择尽可能少的点，但是父亲和儿子至少选一个。
- 令
f[x][0 / 1] 表示在结点x 选 / 不选的情况下，x 子树内的最大独立集点数； 令g[x][0 / 1] 表示在结点x 选 / 不选的情况下，x 子树内的最小点覆盖点数。 - 令根节点为
r ，则答案为\max (f[r][0], f[r][1]) ，\min (g[r][0], g[r][1]) 。
洛谷 P2899 - Cell Phone Network G
- 令
f[x][0 / 1 / 2] 表示x 子树内的最小信号塔数，其中x 被儿子 / 自己 / 父亲覆盖。
洛谷 P4084 - Barn Painting G
- 令
f[x][0 / 1 / 2] 表示x 染成三种颜色的子树内方案数。
树上拓扑序计数
给定一棵外向树（每条边的方向是从父亲到儿子），求其拓扑序个数。
- 多重集合排列数公式：
\frac{(\sum a_i)!}{\prod a_i!} ，a_i 为集合中第i 个元素的数量。 - 令
f[i] 表示i 的子树的拓扑序个数。 -
- 若
i 有k 个儿子j_1, j_2, \cdots, j_k ，则分配位置的方案数为\binom{size[i] - 1}{size[j_1]} \binom{size[i] - 1 - size[j_1]}{size[j_2]} \cdots \binom{size[i] - 1 - size[j_1] - \cdots - size[j_{k - 1}]}{size[j_k]} = \frac{(size[i] - 1)!}{\prod size[j]!} 。 - 然后再乘上
f[j_1]f[j_2] \cdots f[j_k] 。
树上问题
在树上选出
- 令
f[x][i][0 / 1] 表示x 的子树选择i 条链，是 / 否有一条从儿子伸到x 的半链的最大长度和。 - 转移时枚举儿子
y ：-
-
$f[x][j][0] + f[y][i - j][1] + dis(x, y) \to f'[x][i][1]$（半链伸上来）。
-
状压 DP
- 将当前需要用到的状态记录并压缩。
- 例如一般的序列 DP 可能只需要记录
i 表示1 \sim i ，而状压 DP 可能需要记录1 \sim i 中具体哪些位置在状态中。
洛谷 P1171 - 售货员的难题
- 设
f[S][i] 表示从1 \to i 一共经过了村庄集合S 的最短路。 -
- 复杂度为
O(n^2 2^n) 。 - 这与搜索不同之处在于，状压 DP 只关注了去过村庄的集合，而搜索关注访问它们的顺序。在 TSP 问题中，知道访问顺序是没用的。
洛谷 P1559 - 运动员最佳匹配问题
- •与旅行商问题一样，在后面的运动员进行匹配时，我们只关心有哪些运动员已经匹配了，而不关心他们具体是怎么匹配的。这就是状压 DP 相较于普通搜索优化的方式。
- 设
f[i][S] 表示考虑男1 \sim i 号运动员，已经匹配的女运动员集合为S 的最大竞赛优势和。 - 考虑第
i 号男运动员与哪位女运动员匹配了，那么有f[i][S] = \max(\sum f[i - 1][S - j] + P_{i, j} Q_{j, i}) 。
洛谷 P1896 - 互不侵犯
- 按行转移。设
f[i][j][S] 表示前i 行，共j 个国王，第i 行的状态为S 的方案数。
洛谷 P2704 - 炮兵阵地
- 直接转移会导致产生
2^{20} 的状态数，需要预处理。 - 按行转移，记录这一行以及上一行的状态。
洛谷 P2157 - 学校食堂
- 做菜时间的计算式是无关紧要的。
- 由于每个人只允许最多
7 个人插队，那么只需要状压当前结尾7 个人是否已经取餐。 - 设
f[i][j][S] 表示考虑1 \sim i 的人，最后一个取餐的是j ，结尾7 个人取餐的状态为S 的最小总时间。枚举下一个取餐的是谁进行转移。
洛谷 P3226 - 集合选数
-
把一个数的
2 倍排在它下面，3 倍排在它右面，会形成一个网格图，状压每一行选择哪些数。 -
-
两个相邻的点不选即可。