Distance Sum

Time Limit : 4 sec, Memory Limit : 524288 KB

n 個の都市と n − 1 本の道路があり,木になっている.都市には 1 から n までの番号がつけられている.都市 1 を根とみたとき,都市 i の親は pi であり,ipi の距離は di である.すぬけ君は,1 以上 n 以下の各 k に対し,次の問題を解きたい.

ある都市から都市 1, . . . . , k への距離の和の最小値 \begin{eqnarray} min_{1 \leq v \leq n} \{ \sum^k_{i=1} dist(i, v)\} \;\;\;\;\;\;\;\;\;\;\;\;\;\;(2) \end{eqnarray}

を求めよ.ただし dist(u, v)uv の距離をあらわす.

Constraints

  • 1 ≤ n ≤ 200000
  • 1 ≤ pin
  • 1 ≤ di ≤ 200000
  • pi によって表されるグラフは木になっている
  • 入力は全て整数である

Input

n
p2 d2
. . .
pn dn

Output

n 行出力せよ.i 行目には,k = i のときの答えを出力せよ.

Sample Input 1

10
4 1
1 1
3 1
3 1
5 1
6 1
6 1
8 1
4 1

Sample Output 1

0
3
3
4
5
7
10
13
16
19

Sample Input 2

15
1 3
12 5
5 2
12 1
7 5
5 1
6 1
12 1
11 1
12 4
1 1
5 5
10 4
1 2

Sample Output 2

0
3
9
13
14
21
22
29
31
37
41
41
47
56
59

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 2, Tokyo, Japan, 2014-09-13
http://acm-icpc.aitea.net/
http://jag2014summer-day2.contest.atcoder.jp/