春节十二响 题解

题意

给定 𝑛 个程序，每个程序所需内存空间为 𝑚𝑖。

这些程序的调用关系形成一棵以 1 为根的树。

内存可以分为若干个段，每个段存放若干个程序，这些程序在调用关系树上不能为祖先-后代关系，每个段的大小为存放的程序所需空间的最大值。

𝑛 ≤2 ×105

题解

做这种题要先从部分分入手。

它给了一个特殊性质：调用关系为一条链。我们把一个位置的段记到一个集合里，然后分类讨论：

• 只有一个儿子：有依赖关系显然没法扔到一个段里面，所以把 𝑚𝑖 扔到集合里面。
• 两个儿子：一个容易想到的贪心策略，即把两个儿子的段集合里面最大的几个拿出来合并到一个段里面（即取 max）。
  我们用堆来维护这个集合，如果是两个儿子的情况，就取两个儿子的堆顶的 max 放到当前节点的堆中，然后分别弹堆顶，重复这个过程直到一个儿子的堆为空，再把另一个儿子剩下的东西扔到父节点堆里面去就好了。

然后我们发现可以用这个方法直接在树上合并，然后就成了一般情况。对于多个儿子的节点，我们将它们按照第二条规则两两合并，然后扔到父节点的集合里面。

（令 𝑑⁢𝑒⁢𝑝𝑖 表示 𝑖 子树内最深的点的深度。）

发现每次都需要让 max(𝑢,𝑣)⁡𝑑⁢𝑒⁢𝑝𝑣 个程序从一个堆进入到另一个堆里面，一个链带点叶子的结构就会卡到 Θ⁡(𝑛2⁢log⁡𝑛)。

然后我们发现，用到堆的根节点最大的特性的地方，仅有两个儿子堆顶取最大值的地方，除此以外增加复杂度的地方是“把另一个儿子剩下的东西扔到父节点堆里面去”的过程。

后面这个东西相当于合并两个堆，所以如果你已经用了配对堆/斐波那契堆这类 Θ⁡(1) 合并的可并堆那你就可以先走了。

其实我们可以在两个儿子堆顶取最大值后扔到一个缓冲区里面，一个堆空了之后直接把缓冲区里面的东西全都扔到另一个非空堆中，这样就省去了合并的过程。这样的话一次合并的复杂度是 min⁡(𝑑⁢𝑒⁢𝑝𝑥,𝑑⁢𝑒⁢𝑝𝑦) 的。

分析总时间复杂度，发现每一次取 max 实际上就是扔掉一个元素，然后每个元素只能被扔掉一次，总共被扔了 Θ⁡(𝑛) 次，加上堆的影响就成了 Θ⁡(𝑛⁢log⁡𝑛) 次。