3225. 学术报告审核

单点时限: 2.0 sec

内存限制: 256 MB

在东中国正常大学,等级制度森严。每一份学术报告都要经过层层审核。因此上到院长,下到学生,都颇有怨言。但我们不是要解决这个问题,我们只是要算一算每个人在审核学术报告上要花费多少时间。

严格地说,对于一个人 $i$,都有其直系领导 $m_i$,等级数 $r_i$,和阅读 TA 的报告所需要的时间 $t_i$。规定,一个人的报告,要被等级数比 TA 高的上层领导审核,即:不仅要被其领导审核,还要被其领导的领导,以及更高层的领导审核,只要这个领导等级数比 TA 高(确实可能会出现领导等级数反而低的情况)。

例如 Alice 的直系领导是 Bob,Bob 的直系领导是 John,John 的直系领导是 Director,Alice、Bob、John、Director 的等级数分别是 10、20、5、15,那么 Alice 的报告要受到 Bob 和 Director 的审核,Bob 的报告不会受到审核(因为上层领导的等级数没有比他高的),Director 的报告也不会受到审核(因为 TA 没有领导)。

一个人审报告所需要的时间等于 TA 所有要审的下属的报告阅读时间的总和。请求出每个人在审报告上所要花费的时间。

输入格式

第一行一个整数 $N$ $(1 \leq N \leq 10^5)$,表示总人数。

下面是 $N$ 行。第 $i$ 行是三个整数 $m_i, r_i, t_i$ $(1 \leq r_i, t_i \leq 10^5)$,表示编号为 $i$ 的人的直系领导为 $m_i$,等级数 $r_i$,报告阅读时间 $t_i$。有且仅有一位学校最高领导是没有直系领导的,有 $m_i=-1$,其余满足 $1 \leq m_i \leq N$。

领导关系是合法的,也就是说不会出现领导关系成环的情况,也不会出现自己领导自己。

输出格式

输出 $N$ 行。第 $i$ 行一个整数表示编号为 $i$ 的人在审报告上要花费的时间。

样例

Input
5
4 4 80
1 1 40
-1 10 60
3 5 50
4 8 70
Output
40
0
240
120
0

8 人解决,14 人已尝试。

8 份提交通过,共有 46 份提交。

7.1 EMB 奖励。

创建: 3 年,2 月前.

修改: 2 年,10 月前.

最后提交: 2 年,9 月前.

来源: Southwestern European 2016

题目标签