容易发现分配给一个子树的钱只要够了就会移除
具体来讲，如果一个结点被分配到了 \(x\) 块钱，那么有两种情况：
- 子树全部都拿到了该拿的钱，自己拿到了一部分或者全部拿到了
- 对于每个儿子，其子树拿到的钱均不超过某个值
对于情况 1 容易构造使其不发生，对于情况 2 可以每次二分。
\(O(n^2\log V)\) 的算法就是每次跳父亲，然后计算当前节点应该拿多少钱。
考虑对于一个节点 \(u\) 维护一颗平衡树，平衡树上存着子树内所有节点在当前节点的答案。
对于 \(u\) 的某个儿子应该拿到 \(x\) 块钱，那么跳了父亲之后他应该拿到 \(x+\sum\min(sum_v,x)\) 的钱。
容易发现对于 \(u\) 平衡树中每个元素更新后的相对大小是不变的，所以可以更新之后与兄弟的平衡树进行启发式合并。但是更新的复杂度过高。
假设对于 \(x\) 在 \(u\) 的兄弟中满足 \(x>sum\) 比其小的 \(sum\) 之和为 \(S\)，满足 \(x<=sum\) 的节点数量为 \(k\)（包括 \(u\)），那么更新后其值为 \(x\times k+S\)。
可以发现先进行启发式合并后再更新元素的值与先更新再启发式合并是相同的，这样一来复杂度就降低到了 \(O(n\log^2n)\)。
标签：CF1578J,对于,sum,更新,拿到,启发式,节点 From： https://www.cnblogs.com/lmpp/p/17833379.html