CF1578J Just Kingdom

有一棵 $n + 1$ 个点，以 $0$ 号点为根的树，每个节点需要 $m_i$ 的钱。任何一个节点 **在任何时候** 得到总共为 $v$ 的钱的时候，进行以下过程： 1. 查看所有儿子，若还有 $cnt$ 个儿子没有得到足够的钱，那么给每个这样的儿子分发 $\frac{v}{cnt}$ 的钱。 2. 若 $cnt = 0$，则利用 $v$ 的钱尽量满足自己的需要。 3. 如果在 2 中仍然剩下了 $w$ 的钱，全部分给父亲。 注意，当上述儿子或者父亲得到钱的时候，会再次进行这个过程，直到最终全局停止钱的转移。 现在，我们需要对每个 $1\leq i\leq n$，求出 $0$ 号节点一开始获得最少多少的钱，能在上述过程结束之后，满足 $i$ 号节点的需要，这里我们对其他节点不作限制。

无

无

In the sample input, if the king receives $ 5 $ units of tax money, he will split it equally between his vassals — the lords $ 1 $ , $ 3 $ , and $ 5 $ , with each receiving $ \frac{5}{3} $ of money. Lord $ 1 $ will split the money equally between his vassals — $ 2 $ and $ 4 $ , with each receiving $ \frac{5}{6} $ . Lord $ 5 $ will keep the money (having no vassals). Lord $ 3 $ will keep $ 1 $ unit of money, and give the remaining $ \frac{2}{3} $ to the king. The king will then split the $ \frac{2}{3} $ between the vassals with unmet needs — $ 1 $ and $ 5 $ , passing $ \frac{1}{3} $ to each. Lord $ 5 $ will keep the extra cash (now having a total of $ 2 $ , still not enough to meet his needs). Lord $ 1 $ will split it equally between his vassals, and the extra $ \frac{1}{6} $ will be enough to meet the needs of lord $ 4 $ .