시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 2 2 2 100.000%

문제

There are n cities and n − 1 roads, and they form a tree. The cities are numbered 1 through n. The city 1 is the root, and for each i the parent of the city i is the city pi, and the distance between i and pi is di. Snuke wants to solve the following problem for each 1 ≤ k ≤ n:

Compute the minimal possible sum of the distances from a certain city to the cities 1, . . . , k:

\[\min_{1 \le v \le n}{\sum_{i=1}^{k}{dist(i,v)}\]

Here dist(u, v) denotes the distance between cities u and v.

입력

First line of the input contains one integer n (1 ≤ n ≤ 2 · 105). Then n − 1 lines follow, i-th of them contains two integers pi+1 and di+1 — parent of a city i + 1 and the distance between i + 1’th city and its parent (1 ≤ pi ≤ n, 1 ≤ di ≤ 2 · 105, the graph represented by pi is a tree).

출력

Print n lines. In the i-th line, print the answer when k = i.

예제 입력 1

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

예제 출력 1

0
3
3
4
5
7
10
13
16
19

예제 입력 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

예제 출력 2

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