dfs 序优化树上依赖性背包学习笔记

我们知道对于树上背包，若每个结点上只有总大小为 $O(1)$ 的物品，则总复杂度为 $O(n^2)$；若再限制背包大小为 $m$，则总复杂度为 $O(nm)$。

但问题在于，这些实现无法解决多重背包，亦无法解决物品大小不为 $1$ 的情况。此时，一个结点子树内的总物品数不再与子树大小同级，不适用之前的复杂度分析，由于在每个结点上我们都需要对儿子的背包进行非平凡的合并，总复杂度容易上升至 $O(nm^2)$。dfs 序优化的树上依赖性背包则避免了合并背包这一操作。

形式化的，树上依赖性背包指的是这样一类问题：若在某结点上选取了物品，则必须在其所有祖先上选取物品。

我们考虑直接在树的 dfs 序上进行 dp，在每个结点处我们都有两种决策：

选取至少一个物品，然后进入子树继续选取物品。
什么都不选，跳过当前子树。

设 $f_i$ 表示考虑了 dfs 序上前 $i$ 个结点后的背包数组，使用刷表法进行的 dp 转移形如：
$$
\begin{array}{c}
f_i+\text{at least one item} \to f_{i+1}\\
f_i \to f_{i+siz_i}
\end{array}
$$
注意这里转移中对背包的合并是平凡的，也即直接对每个点值取 $\max$。

void merge(const std::vector<int> &from, std::vector<int> &to){
    for(int i = 0; i < from.size(); i++){
        to[i] = std::max(from[i], to[i]);
    }
}

dfs 序优化的树上依赖性背包相当于是拿着同一个背包在树上走了一圈。由于没有合并操作，复杂度瓶颈只在于进行单次背包本身的复杂度。令背包容量为 $m$，物品个数为 $c$，如果使用二进制分组优化多重背包，则总复杂度为 $O(nm\log c)$；如果使用单调队列优化多重背包，则总复杂度为 $O(nm)$。物品大小不为 $1$ 的 01 背包复杂度为线性。

值得一提的是，dfs 序优化树上依赖性背包也有多种风格的实现方式。

显式做法。求出 dfs 序后在 dfs 序上 dp。

  std::vector<int> dfn, f[N];
  void dfs(int u){
      siz[u] = 1;
      dfn.push_back(u);
      for(int v: son[u]) dfs(v), siz[u] += siz[v];
  }
  void solve(){
      dfs(rt);
      for(int i = 0; i < dfn.size(); i++){
          int u = dfn[i];
          merge(f[i], f[i + siz[u]]);
          // add at least one item to u's backpack (f[i])
          // and name the new backpack modified_backpack
          merge(modified_backpack, f[i + 1]);
      }
  }

当然也可以使用填表的写法，需要倒序转移。

隐式做法。直接在 dfs 的过程中完成转移。$f_u$ 在进入 dfs 时考虑了 dfs 序在 $u$ 之前的结点，在结束 dfs 时也处理了 $u$ 的所有子树。钦定 $u$ 中至少选取一件物品。
```
  std::vector<int> f[N];
  void dfs(int u){
      // add at least one item to u's backpack (f[u])
      for(int v: son[u]){
          f[v] = f[u];
          dfs(v);
          merge(f[v], f[u]);
      }
  }
```
这里我们只显示的进行了选取物品并进入子树的决策，而跳过子树的决策则隐式的在父亲的 merge 过程中进行。

例题

LG3780 [SDOI2017] 苹果树

使用上面提到的隐式做法可以使实现更加简洁，思路更加清晰。隐式做法允许我们在到达一个结点时特殊处理该结点到根的链，在回溯过程中再复原 dp 数组。

LG6326 Shopping

树上依赖性背包选取的是包含根的连通块，而本题中则要求选取任意连通块。

于是我们使用 dfs 序优化背包 + 点分治即可。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。