거리 합

도시가 $n$개 있고 도로가 $n - 1$개 있다. 이들은 트리를 이룬다. 도시에는 1번부터 $n$번까지 번호가 붙어 있으며, 1번 도시가 루트이다. 각 $i$에 대해 도시 $i$의 부모는 도시 $p_i$이고, $i$와 $p_i$ 사이의 거리는 $d_i$이다.

스누크는 각 $1 \le k \le n$에 대해 다음 문제를 풀려고 한다. 한 도시에서 도시 $1, \ldots, k$까지의 거리 합이 가능한 최솟값을 구한다. 즉, 다음 값을 계산한다.

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

여기서 $dist(u, v)$는 도시 $u$와 $v$ 사이의 거리이다.

첫째 줄에 정수 $n$($1 \le n \le 2 \times 10^5$)이 주어진다. 이어지는 $n - 1$개의 줄에는 도시 $i + 1$의 부모 $p_{i+1}$과 도시 $i + 1$과 부모 사이의 거리 $d_{i+1}$이 각각 두 정수로 주어진다($1 \le p_i \le n$, $1 \le d_i \le 2 \times 10^5$). $p_i$로 표현되는 그래프는 트리이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $k = i$일 때의 답을 출력한다.