P6326 Shopping 题解

· · 题解

前言

一个经典的按 DFS 序转移与点分治题目，在 2018 国家集训队论文的《解决树上连通块问题的一些技巧和工具》一文中有较为完整的总结。

本题属于树上连通块 DP 问题，这类问题一般有两种形式：

  1. 计数类问题：给定树 T 和性质 A，查询树上满足性质 A 的连通块数量。
  2. 最优化问题：给定树 T 和价值函数，查询树上所有满足某性质的连通块的最优价值。

显然本题就是一类最优化问题，价值函数为背包。

题解

本题的朴素做法是直接记录 f_{i, j} 表示对于在子树 i 内包含 i 的所有连通块，花费 j 元可以得到的最大价值。

一个比较明显的特征是，这个 dp 需要合并子树，而背包合并的复杂度是 O(m^2) 的（m 为值域）。相反，加入一个点（物品）的复杂度是 O(m) 的（单调队列优化，也可以用二进制分组做到 O(m\log d) 的复杂度）。

对于这类合并信息不够高效，但是加入单点的信息比较高效的问题，往往可以按照 DFS 序转移，把合并子树变成加入单点。树上背包就是一个典型的例子。

设 f_i 表示考虑 DFS 序上 [i, n] 这些节点的答案。则 f_1 可以由 [2, n] 的答案添加物品 1 转移。

一般的，f_i 可以由 \operatorname{add}(f_{i+1}, \mathrm{item}_i) 转移，表示添加 i 物品。如果不选择 i，则也不能选择 i 的子树，所以另一个是直接由 f_j 转移，这里的 j 是 i 子树在 DFS 序上的右端点 +1。

但是有个问题……这里的 DFS 序转移是以 1 为根的，换句话说，f_1 的结果是必须选择 1 的答案（不选择就是 0 了）。不过解决方案也很简单，直接对树进行点分治便可以考虑所有情况。即考虑强制选择重心的情况，否则递归下去处理。

总时间复杂度 O(nm\log n)。