Just Kingdom

题意翻译

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

题目描述

The Just Kingdom is ruled by a king and his $ n $ lords, numbered $ 1 $ to $ n $ . Each of the lords is a vassal of some overlord, who might be the king himself, or a different lord closer to the king. The king, and all his lords, are just and kind. Each lord has certain needs, which can be expressed as a certain amount of money they need. However, if a lord, or the king, receives any money, they will first split it equally between all their vassals who still have unmet needs. Only if all the needs of all their vassals are met, they will take the money to fulfill their own needs. If there is any money left over, they will return the excess to their overlord (who follows the standard procedure for distributing money). At the beginning of the year, the king receives a certain sum of tax money and proceeds to split it according to the rules above. If the amount of tax money is greater than the total needs of all the lords, the procedure guarantees everybody's needs will be fulfilled, and the excess money will be left with the king. However, if there is not enough money, some lords will not have their needs met. For each lord, determine the minimum amount of tax money the king has to receive so that this lord's needs are met.

输入输出格式

输入格式

The first line of the input contains the number of lords $ n $ ( $ 0 \le n \le 3 \cdot 10^5 $ ). Each of the next $ n $ lines describes one of the lords. The $ i $ -th line contains two integers: $ o_i $ ( $ 0 \le o_i < i $ ) — the index of the overlord of the $ i $ -th lord (with zero meaning the king is the overlord), and $ m_i $ ( $ 1 \le m_i \le 10^6 $ ) — the amount of money the $ i $ -th lord needs.

输出格式

Print $ n $ integer numbers $ t_i $ . The $ i $ -th number should be the minimum integer amount of tax money the king has to receive for which the needs of the $ i $ -th lord will be met.

输入输出样例

输入样例 #1

5
0 2
1 2
0 1
1 1
0 5

输出样例 #1

11
7
3
5
11

说明

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 $ .