看到课程标题是 “DP优化”，以为就是斜率优化、单调性之类的……
结果来了些什么奇妙操作
# 题面
给定一棵 $n$ 个点的树和整数 $m$，每个点有两类权值 $a_i,b_i$。
对于每个 $h=1\sim m$，求树上的一个独立集 $S$，使得 $\sum\limits_{i\in S}a_i\le h$，且 $\sum\limits_{i\in S}b_i$ 最大，输出满足上述条件的 $S$ 的数量。
数据规模：$n\le50,m\le5000,1\le a_i\le m,b_i\le 10^6$。
# 解析
题面就描述了一个背包问题，另外有独立集的限制。
如果在原树上直接背包，需要背包合并（由于物品大小并非 $1$，虽然两个点只会在 LCA 处产生贡献，但是合并的复杂度仍然是 $\mathcal{O}(m^2)$ 的），复杂度只能是 $\mathcal{O}(nm^2)$，无法再优化。
话不多说，我们直接来看看怎么用神仙操作来做这道题。
首先我们建出原树的点分树，点分树有两个（重要的）性质，其中一条我们非常熟悉：
- 树高是 $\mathcal{O}(\log n)$。
另外一条非常显然但是不常用（至少我没见过哪道题用）：
- 原树上与 $u$ 相邻的点在点分树上只可能是 $\mathbf{u}$ 的祖先 和 $u$ 的后继。
怎么利用这两点来解题？我们考虑按照点分树的 DFS 序 依次决策每个节点是否在独立集中。
这样的话，当我们决策 $u$ 时，就不需要考虑 $u$ 的后继是否选入独立集，而只需要考虑 $\mathbf{u}$ 的祖先 有哪些被选入了独立集中 —— $u$ 的祖先不多，只有 $\mathcal{O}(\log n)$ 个，于是可以状压：$f_{u,s,i}$ 表示的状态为「已经决策了 $u$，从根到 $u$ 的链上被选入独立集的点是 $s$（压缩状态），且当前背包中装了总重为 $i$ 的物品」，需要维护对应的物品价值最大值以及方案数。
那么 $s$ 的范围是 $\mathcal{O}(2^{\log n})=\mathcal{O}(n)$ 的，$f_{u,s,i}$ 的状态数是 $\mathcal{O}(n^2m)$ 的。由于是 0-1 背包，可以 $\mathcal{O}(1)$ 转移，总的复杂度也是 $\mathcal{O}(n^2m)$ 的。
下面关于一些细节简单说一下：
- 知道了祖先的选定状态 $s$，如何判断 $u$ 是否能加入当前的独立集中？为了保持复杂度必须 $\mathcal{O}(1)$ 判断：
- 维护压缩状态
lnk[u]表示当前点分树的祖先中，哪些是原树上与 $u$ 相连的节点。 - 判断只需要判断
lnk[u]和 $s$ 是否有交； - 维护只需要在 DFS 进入点 $u$ 时枚举原树上与 $u$ 相邻的点 $v$，更新
lnk[v]，DFS 退出点 $u$ 时在lnk中撤销 $u$ 的信息即可。
- 维护压缩状态
- $f_{u,s,i}$ 中压缩状态 $s$ 的维护：记 $u$ 在 DFS 序上的前驱为 $v$，我们需要从 $f_v$ 转移到 $f_u$。
- 只需要深度小于 $dep_u$ 的祖先；
- 就需要把 $f_{v,s,i}$ 的 $s$ 中深度大于等于 $dep_u$ 的部分删去；
- 具体的，在 DFS 退出点 $u$ 时，对每个 $s\ge 2^{dep_u}$，将 $f_{u,s,i}$ 贡献到 $f_{u,s-2^{dep_u},i}$；
- 这样的效果就是递归到当前层时，有用的 $s$ 的位数不超过 $dep_v-1$。
大概是一个不错的处理独立集的方法……
# 源代码
1 | /*Lucky_Glass*/ |