题目描述

有 $n$ 个城市和 $n-1$ 条道路，形成一棵树。
把城市从 $1$ 到 $n$ 的编号，以城市 $1$ 为根，城市 $i$ 的父节点是 $p_i$，$i$ 和 $p_i$ 的距离是 $d_i$。

对于每个 $k$（$1\le k\le n$），求每一个城市到城市 $1\sim k$ 距离之和的最小值

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

$dist(u,v)$表示 $u$ 和 $v$ 的距离。

输入格式

第一行为一个整数 $n$， 下面 $n-1$ 行为两个整数 $p_i$ $d_i$。

n
p2 d2
· · ·
pn dn

输出格式

输出共 $n$ 行，
在第 $i$ 行中，输出 $k＝i$ 时的答案。

输入输出样例

样例 #1

样例输入 #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
14

样例 #2

样例输入 #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

提示说明

• $1 ≤ n ≤ 200000$

• $1 ≤ p_i ≤ n$

• $1 ≤ d_i ≤ 200000$

• $p_i$ 表示的图表是树

• 输入全部为整数