An AQT Problem

View as PDF

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

Author:
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

5
0 0
1 2
1 100
2 3
4 1

Sample Output

0 2 100 5 6