更佳的阅读体验：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$ 染成三种颜色的子树内方案数。
树上拓扑序计数
给定一棵外向树（每条边的方向是从父亲到儿子），求其拓扑序个数。$n \le 10^5$。
- 多重集合排列数公式： $\frac{(\sum a_i)!}{\prod a_i!}$，$a_i$ 为集合中第 $i$ 个元素的数量。
- 令 $f[i]$ 表示 $i$ 的子树的拓扑序个数。
- $i$ 子树内首先第一位必须是 $i$，然后剩下的 $size[i] - 1$ 个位置需要分配给其儿子的子树。
- 若 $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]$。
树上问题
在树上选出 $m$ 条边互不相交的链，使得他们的长度和最大。$n \le 10^5$，$m \le 10$。
- 令 $f[x][i][0 / 1]$ 表示 $x$ 的子树选择 $i$ 条链，是 / 否有一条从儿子伸到 $x$ 的半链的最大长度和。
转移时枚举儿子 $y$：
- $f[x][j][0] + f[y][i - j][0] \to f'[x][i][0]$，$f[x][j][1] + f[y][i - j][0] \to f'[x][i][1]$（树形背包）。
- $f[x][j][1] + f[y][i - j - 1][1] + dis(x, y) \to f'[x][i][0]$（半链合并）；
$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$ 的最短路。
- $f[S][i] = \min(f[S - i][j] + dis[j, i])$。
- 复杂度为 $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$ 倍排在它右面，会形成一个网格图，状压每一行选择哪些数。
- $\mod 6 = 1, \mod 6 = 5$ 的数字会位于左上角。
- 两个相邻的点不选即可。