春节十二响 题解

题意

给定 \(n\) 个程序，每个程序所需内存空间为 \(m_i\)。

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

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

\(n\leq 2\times 10^5\)

题解

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

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

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

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

（令 \(dep_i\) 表示 \(i\) 子树内最深的点的深度。）

发现每次都需要让 \(\max_{(u,v)} dep_v\) 个程序从一个堆进入到另一个堆里面，一个链带点叶子的结构就会卡到 \(\Theta(n^2 \log n)\)。

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

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

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

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