题意：给出一棵有根树，每个节点上有无穷多个物品，购买节点
的一个物品需要花费 元。
记节点 的物品购买了 个。则需要满足 ，其中
为给定常数。
问在有
元的情况下最多购得多少个物品。
，，时限 。
将 数组做树上差分，记 ，则 。
而将 增加 所需的代价是子树 内 的和。而受益则为子树 的大小。
现在问题变成了
个物品的多重背包。（注意根不受
的限制）
很大，直接 不可行。
不难想到一种贪心，即按照性价比选择，可惜的是，这个贪心是错误的。
这个贪心能排除一些较劣的解，简化决策 : 若有两个物品 满足 ，且
，显然可以将 个 换成 个 ，这样收益没有变化，但是代价减少了。
这告诉我们，购买某个物品个数超过 的部分可以贪心调整。所以每个物品保留
个做背包，区其余按照性价比贪心即可。
设 为获得收益为
时最小的成本，类似多重背包转移即可。使用二进制拆分实现，复杂度为 。