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 国际许可协议 进行许可。