\(\text{Luogu P1552 [APIO2012] 派遣}\)
前置芝士：可并堆（左偏树）或 斜堆 或 启发式合并。
本题题意概括为：给定一颗以 \(1\) 为根的树，每个点有权值 \(L_i\)，花费 \(C_i\)，可以选择一个以某个结点为根的子树，并从其中选出一个点集 \(T\) 满足 \(\sum_{i\in T} C_i \leq M\)，那么此次的价值就是这个结点的 \(L_i\times |T|\)。求最大价值。
显然，每个点选择的点集肯定是将子树中点从小到大一直选，直到和大于 \(M\)，这样选出来的点集的大小才最大，我们不妨不考虑选点，而是考虑删点，将子树中的点从大到小开始删去，直到和小于等于 \(M\)，那么这个可以用大根堆维护。每次加入子树中的点会每次都 \(O(n\log n)\) 操作，由于是子树问题，可以考虑直接把儿子结点的堆合并起来，使用启发式合并，总时间复杂度为 \(O(n\log n)\)。
标签：结点,子树,Aug,Problems,Ideas,2024,为根 From： https://www.cnblogs.com/LaDeX-Blog/p/18354098/2024-Aug-Idea-Problem