树上背包上下界优化

前言

看到一个比较牛（sao）的复杂度证明，记一下。

基本的树上背包问题长这样（就是把花费为1的0-1背包搬上了树）：现在有 $n$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $m$ 门课程学习，问他能获得的最大学分是多少？（$1 \leq N , M \leq 3000$）

树形背包的复杂度是 $O(nm^2)$，比起平时背包的 $O(nm)$ 差多了去了。但树形背包真的可以 $O(nm)$。

代码与思想

核心代码（优化后，选自OIWIKI）：

int dfs(int u) {
      int p = 1;
      f[u][1] = s[u];
      for (auto v : e[u]) {
        int siz = dfs(v);
        // 注意下面两重循环的上界和下界
        // 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
        for (int i = min(p, m + 1); i; i--)
            for (int j = 1; j <= siz && i + j <= m + 1; j++)
                f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
        p += siz;
      }
      return p;
}

注意如上代码中，每个数都肯定都只会被合并前的的f更新，所以不会出现“完全背包”的情况。

递归，在访问完每个子树时求解。设 $i$ 点花费为 $v_i$，收益为 $w_i$，$siz_i$ 表示点 $i$ 在访问到当前子树时所有访问过的字树的价格和与点 $i$ 的和，$f_{i,j}$ 为点 $i$ 中给 $j$ 点“价值”时的最大收益。在普通DP式 $f_{u,j}=\max\{f_{i,j},f_{i,j-k-v_i}+f_{v,k}+w_i\}$ 的基础上添加限制 $j\leqslant{siz_u},k\leqslant{siz_v}$ 即可。

证明

这个DALAO证得太好了，我就不写了其实虽然这个DALAO讲的十分好懂，但考虑到 $n$ 和 $m$ 同级，这样做似乎没有必要。

后话

以 $O(nm^2)$ 都可以过的此题为例虽然就5个点，还是比$O(nm^2)$快不少：