16844번 - 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 p_i, and the distance between i and p_i is d_i. 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 · 10⁵). Then n − 1 lines follow, i-th of them contains two integers p_i+1 and d_i+1 — parent of a city i + 1 and the distance between i + 1’th city and its parent (1 ≤ p_i ≤ n, 1 ≤ d_i ≤ 2 · 10⁵, the graph represented by p_i is a tree).

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