CF1578J.Just Kingdom

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.

正义王国由一位国王和 $n$ 位领主统治，领主编号为 $1$ 至 $n$。每位领主都效忠于某位上级领主（即“宗主”），该宗主可能是国王本人，也可能是更靠近国王的另一位领主。国王及所有领主均公正而仁慈。

每位领主都有特定的需求，可表示为满足其需求所需的一定金额。然而，若某位领主或国王收到任何资金，他们将首先将这笔钱平均分配给所有尚未满足需求的直属封臣（vassal）。仅当其所有直属封臣的需求均已满足后，他们才会动用剩余资金来满足自身需求。若在满足自身需求后仍有结余，他们便将多余的资金返还给自己的宗主（宗主亦遵循上述资金分配规则）。

每年年初，国王会收到一笔税款，并依据上述规则进行分配。若税款总额大于所有领主需求之总和，则该分配过程可确保所有领主的需求均被满足，且多余资金将留存在国王处。然而，若税款不足，则部分领主的需求将无法被满足。

对每一位领主，请确定：国王至少需收到多少税款，才能确保该领主的需求得到满足。

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 \lt 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.

输入的第一行包含领主的数量 $n$（$0 \le n \le 3 \cdot 10^5$）。接下来的 $n$ 行每行描述一位领主。第 $i$ 行包含两个整数：$o_i$（$0 \le o_i \lt i$）—— 第 $i$ 位领主的上级领主的索引（其中 $0$ 表示国王为其上级领主），以及 $m_i$（$1 \le m_i \le 10^6$）—— 第 $i$ 位领主所需的资金数额。

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.

输出 $n$ 个整数 $t_i$。其中第 $i$ 个数应为国王需收取的最少整数金额的税款，使得第 $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$.

在样例输入中，如果国王收到 $5$ 单位的税收，他将把这些钱平均分给他的封臣——领主 $1$、$3$ 和 $5$，每人获得 $\frac{5}{3}$ 单位的钱。

领主 $1$ 将把所得的钱平均分给他的封臣——领主 $2$ 和 $4$，每人获得 $\frac{5}{6}$。领主 $5$ 将保留全部所得（因其没有封臣）。领主 $3$ 将留下 $1$ 单位的钱，并将剩余的 $\frac{2}{3}$ 交还给国王。随后，国王会将这 $\frac{2}{3}$ 平均分给尚未满足需求的封臣——领主 $1$ 和 $5$，每人分得 $\frac{1}{3}$。领主 $5$ 将保留这笔额外资金（此时共持有 $2$ 单位，但仍不足以满足其需求）。领主 $1$ 将把这笔额外资金平均分给他的封臣，其中额外的 $\frac{1}{6}$ 足以满足领主 $4$ 的需求。