[ARC096F] Sweet Alchemy
Atcoder：[ARC096F] Sweet Alchemy
Solution
将原题限制转化为父节点 \(p_i\) 向子节点 \(i\) 连边，把选取单点转化为选取子树，相当于做了一次差分，这样选取任意一个点的子树的次数都不能超过 \(d\)（根节点对应的整棵树除外）
这是一个显然的多重背包问题：选取一个子树 \(T\)，对应体积 \(v_i = \sum\limits_{x \in T}m_x\)，价值 \(w_i = size_T\)，最多选 \(d\) 次（根节点对应的整棵树除外）。
但是体积和物品数量都是 \(10^9\) 级别的，常规的多重背包根本没法做。
贪心
这个题最厉害的地方就是把背包和贪心结合在一起。
众所周知，按 \(\frac{w_i}{v_i}\) 从大到小排序尽量多选的方法是错误的，但不妨考虑这个贪心在什么时候是对的。
尽可能地把绝大多数规模的问题划归到一个正确的贪心上以保证时间复杂度正确。
假设现在有物品 \(i, j\)，\(\frac{w_i}{v_i} > \frac{w_j}{v_j}\)，即 \(w_iv_j > w_jv_i\)，可以看作是选 \(w_i\) 个 \(j\) 物品的体积大于选 \(w_j\) 个 \(i\) 物品的体积。同时两种选取方式的价值都是一样的，为 \(w_iw_j\)，因此 选 \(w_j\) 个 \(i\) 物品一定优于选 \(w_i\) 个 \(j\) 物品。
当选择的 \(i\) 物品数量超过 \(w_j\) 个时，\(j\) 物品最多选 \(w_i - 1\) 个。
记 \(c_x\) 表示物品 \(x\) 的选取个数，则不可能出现 \(c_i \le d - w_j\) 且 \(c_j \ge w_i\) 的情况，因为可以把 \(w_i\) 个 \(j\) 物品换成 \(w_j\) 个 \(i\) 物品。
借洛谷题解里的这个图：
可知中间部分的贪心是正确的，也即中间部分不可能有两个没填满的柱子。
把每个物品取 \(\min(d, n)\) 个出来做多重背包（\(n\) 对应物品价值的上界），剩下的就按 \(\frac{w}{v}\) 从大到小能选就选。
此时多重背包价值和的上界为 \(n^3\)，于是背包时将价值与体积倒过来处理。