Distance Sum

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.