Problem2392--暑假提高组模拟测试卷十 T3 怪物猎人

2392: 暑假提高组模拟测试卷十 T3 怪物猎人

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:][下载测试数据]

Description

由于拉诺亚王国出现了一个怪物巢穴，工会新发布了一个A级任务进行清剿，为了能让自己的名声扩散出去，鲁迪乌斯决定接下这个任务。

经过一段时间的观察，鲁迪乌斯发现怪物巢穴类似一棵树的结构，巢穴的入口只有一个，在 1 号节点上（也即 1 号节点为根）。树上每个节点都有一个血量为 hp_i 的怪物。由于怪物们的天赋能够使用联合技能，打败每个点的怪物 i 所需要的能量值为 hp_i + 所有存活的直接子节点 j 的 hp_j。由于巢穴的结构问题，每次必须要消灭父节点的怪物后后才能消灭子节点的怪物。

鲁迪乌斯如今已经是一个非常厉害的法师了，他之前制作了 m 个魔咒，每个魔咒可以不耗费能量且可以消灭任意一个存活的怪物。他想知道当 m=0，1，2，3…，n 时的最低总能量花费分别为多少。



Input

第一行输入一个数 n ，表示树的节点个数。

接下来 n-1 行，每行输入两个数 x, y, 表示 x 到 y 有一条边。

最后一行输入 n 个数 hp_1, hp_2, ..., hp_n ，表示怪物的血量。



Output

输出一行，n+1 个数字，使用单个空格分开，依次表示 m=0,1,2,...,n 时所需要花费的最小代价。

Sample Input

## 样例 #1

### 样例输入 #1

```
5
1 2
2 3
3 4
4 5
1 2 3 4 5
```

### 样例输出 #1

```
29 16 9 4 1 0
```

## 样例 #2

### 样例输入 #2

```
12
1 2
2 3
2 4
4 5
5 6
3 7
4 8
3 9
8 10
10 11
11 12
9 1 3 5 10 10 7 3 7 9 4 9
```

### 样例输出 #2

```
145 115 93 73 55 42 32 22 14 8 4 1 0
```

HINT

对于所有的数据，满足 1< n < 2000, 1< hp_i < 10^9 。

子任务编号 n 特殊性质 分值
1 2 <= n <= 10 无 20
2 2 <=n <= 100 无 20
3 2 <=n <=2000 树的形态为一条链 20
4  2 <= n <= 2000 无 40


Source/Category

 

[Submit] [Status]