树形 DP
369Pai
·
·
个人记录
树形 DP - OI Wiki
子树合并背包类型的dp的复杂度证明 - cervoliu（上下界优化）
树上背包及其优化详解 - 星夜（dfs 序优化，泛化物品）
《浅谈几类树上背包问题》 - 徐持衡（泛化物品）
树上背包
上下界优化
在物品带有体积时会爆炸，时间复杂度为 \mathcal{O}(nmw)，其中 m 是背包容量，w 是最大体积。
可以发现在证明中，极大的小子树大小之和与极小的大子树大小之和都会由 nm 变成 nmw，就假在这里。
泛化物品
我们定义泛化物品为没有固定的费用（体积）和价值，价值与费用（体积）成函数关系的物品。泛化物品可以用一个一维数组 f 来描述，其中 f_i 意义为在体积为 f_i 时泛化物品 f 的价值。
泛化物品之和：
时间复杂度 $\mathcal{O}(m^2)$。
泛化物品和一个物品之和:
$f(i) = \min\{f(i),f(i-v)+w\}(v \le i \le m)
泛化物品之并：
设以 $u$ 为根的子树，处理好了儿子 $v$ 之前的儿子与 $u$ 的泛化物品之和。
那么将当前的 $f_u$ 中强制放入物品 $v$ 作为 $f_v$ 的初始状态，那么处理完以 $v$ 为根的子树后，$f_v$ 就是与 $f_u$ 有交的泛化物品，将 $f_v$ 与 $f_u$ 取并就能得到处理完 $v$ 及之前的儿子的泛化物品之和。
### dfs 序
将树根据 dfs **离开**节点的顺序编号。
按 dfs 序从小到大遍历，每个节点 $i$ 在加入时一定是当前子树的根，同时不在以 $i$ 为根的子树内的点是前 $i-sz_i$ 个点。
$$f_{i,j}=\max(f_{i-1,j-v_i}+w_i,f_{i-sz_i,j})$$
## 例题
[$\textbf{CF1794E Labeling the Tree with Distances }$](https://www.luogu.com.cn/problem/CF1794E)
对于每个点 $x$，求出以它为根时距离集合。集合只需判等，用哈希表示。
哈希函数为 $\sum P^{dis_u}$，即 $\sum\limits_{i=0}^{maxdep}cnt_i \times P^i$。
考虑换根 DP，设 $f_i$ 表示原树以 $i$ 为根子树的答案，$g_i$ 表示以 $i$ 为树根时，扣掉原树中以 $i$ 为根的子树的答案。
$f_i$ 可以在扫描时预处理出来 $f_u=1+\sum\limits_{v\in \mathrm{son}(u)}{P\times f_v}$。
换根时计算 $g_v = P \times (g_u+f_u- P \times f_v)$。
[$\textbf{P2606 [ZJOI2010] 排列计数 }$](https://www.luogu.com.cn/problem/P2606)
发现从小到大插并不能做。
考虑限制是树形关系，并且与**绝对大小**无关，那么设 $f_u$ 表示以 $u$ 为根的子树是 Magic 的方案数，首先根是最小的，在相对大小为 $2\dots sz_u$ 的数中选出 $1\dots sz_{lson}$ 个数放入左子树，方案数为 $\binom{sz_u - 1}{sz_{lson}} $，那么转移方程就是 $f_u=\binom{sz_u - 1}{sz_{lson}}\times f_{lson} \times f_{rson}$。
[$\textbf{[ABC160F] Distributing Integers}$](https://www.luogu.com.cn/problem/AT_abc160_f)
排列计数换根版。
考虑多个子树的情况，本质上是将 $sz_u-1$ 个数分进大小为 $sz_{v_1},sz_{v_2},\dots,sz_{v_k}$ 的桶中，由于每个桶中不考虑顺序，所以方案数是 $\frac{(sz_u-1)!}{\prod\limits_{v \in \mathrm{son}(u)}sz_v}$。
所以 $f_u = (sz_u-1)! \prod\limits_{v \in \mathrm{son}(u)}\frac{f_v}{sz_v}$。
换根时将 $v$ 的影响从 $u$ 中去除，再将 $u$ 对 $v$ 的贡献计算一下即可。
[$\textbf{Permutation on Tree }$](https://codeforces.com/gym/104373/problem/H)
[$\textbf{Vasya and Maximum Matching }$](https://www.luogu.com.cn/problem/CF1032F)
手玩可以得出结论：树的最大匹配唯一当且仅当它是完美匹配或者只有一个孤点。
略证：如果最大匹配唯一，可以反证叶节点一定在匹配中，然后不停删掉叶子和其父亲匹配即可归纳证明。
设计 DP 状态 $f_{u,0/1/2}$ 表示以 $u$ 为根的子树，$u$ 是孤点 / 与儿子匹配 / 与父亲匹配的方案数。
$u$ 是孤点时，不能和父亲或儿子有连边，不然会导致匹配不唯一，所以只能断掉和儿子的所有边。
$u$ 与父亲匹配时，不能和是孤点的儿子有连边，但是和与孙子匹配的儿子有无连边都没关系，所以 $2 \times f_{v,1}$。
$u$ 与儿子匹配时，一个儿子要与父亲匹配，其他儿子只能是孤点或者与孙子匹配，非孤点的同样有无连边都没关系。
$f_{u,0} = \prod f_{v,0}+f_{v,1}$；
$f_{u,2} = \prod f_{v,0}+2f_{v,1}$；
$f_{u,1} = \prod f_{v,2}\prod f_{w,0} + 2f_{w,1}$。
中间部分可以预处理前缀后缀积做到线性转移。
[$\textbf{模拟退火}$](https://ac.nowcoder.com/acm/contest/51727/D)
~~虽然但是，模拟退火能过~~
当 $n$ 比较小时，可以通过枚举每个点是否操作，将剩下的边用一操作删除的方式 $\mathcal{O}(n2^n)$ 计算答案。
考虑树的情况，设 $f_{u,0/1}$ 表示以 $u$ 为根的子树，不用/用操作二，删完子树内所有边的最小代价。
$f_{u,0} = \sum\min(f_{v,0}+a , f_{v,1})$；
$f_{u,1} = b + \sum\min(f_{v,0} , f_{v,1})$。
发现可以扣出一颗生成树，剩下的边 $(u,v)$ 通过钦定被 $u$ 或 $v$ 删除或直接删边，将图的问题转化为树上的问题（有一些点必须用操作二）；时间复杂度 $\mathcal{O}(n3^{m-n+1})$。
这样还是不够优秀，实际上可以运用**反悔**的思想，钦定 $(u,v)$ 被某一端点删除，如果某个点不使用操作二，那么需要加上 $a\times\text{钦定被这个点删除的边数}$ 的代价，时间复杂度 $\mathcal{O}(n2^{m-n+1})$。
两个算法根号分治一下，就能在 $\mathcal{O}(n2^{\frac{n}{2}})$ 之内 解决问题，注意要分别对于每个连通块做，不然生成树不能扣掉 $n-1$ 条边。