AT_icpc2014summer_day2_h Distance Sum
题目描述
有 $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$ 表示的图表是树
- 输入全部为整数