An AQT Problem

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type

AQT is trying to get better at programming. However, he can't, despite his best efforts, and as such has resorted to copying code. He wishes to copy code from coder a_N. Little does he know, code a_N copies from coder a_{a_N}. In fact, coder a_{a_N} also copies code from code a_{a_{a_N}}. This continues to form a tree, up until coder 1, who writes his own code. AQT is a leaf node, that is, no one copies code from him. There are many other leaf nodes, such as BQT, and CQT.

AQT is guaranteed to be coder N.

Copying code takes time. Coder i takes k_i minutes to copy the code from coder a_i. Coder 1 will have a k_i = 0, as he does not copy code.

Coder 1 has just written a new piece of code at time 0. AQT would like to know how long it will take for a coder i to copy it. He wants to know for all coders i (1 \le i \le N).

Input Specification

The first line will contain the integer N (1 \le N \le 10^5), the number of coders.

The next N lines will each contain two integers, a_i, k_i (0 \le a_i < i, 0 \le k_i \le 100). Coder 1 will have a_1 = 0, k_1 = 0. All other coders will have a_i > 0, k_i > 0.

Output Specification

Output N integers on one line, the i^{th} integer indicating the amount of minutes it takes for coder i to copy the code.

Sample Input

0 0
1 2
1 100
2 3
4 1

Sample Output

0 2 100 5 6


There are no comments at the moment.