Educational Codeforces Round 110 Gold Transfer 题解 (C++ only)

题解

首先，因为子节点的cost一定高于其父亲节点。因此显而易见的，我们会优先选择深度更低的节点。于是我们立刻想到要快速的找到深度最浅且仍有剩余黄金的节点。

于是我们很自然的想到二分的方式。以一个深度为9的节点为例，倍增的建立一个其祖先节点位置的索引：

假如1号节点没有黄金且5号节点有黄金。但由于不知道2-4号的节点是否有黄金，因此我们从5号节点出发继续找：

以此类推，我们可以O(logn)的得到深度最浅的有黄金的节点。然后我们在这个节点尽可能多的购买。如果不够就再重新从9号节点做一次即可。

至于为什么这样不会超时呢？因为我们可以发现，对于一次购买，最坏的情况是：某一个节点买了一部分，但这个节点的所有父亲全部都被买空。
因此，一旦某个子节点空了，则其所有父亲节点一定是空的。因此虽然我们会多次找最浅的节点，但除了最后一次，其他的重复在整个查询过程中只会出现一次（因为这一次过后，就一定是0，不再出现）。

代码

C++

Java

TLE在26组。但其实完全和我的C++代码是完全同样的做法，但C++过了。