#P7394. [2019雅礼集训]货运
[2019雅礼集训]货运
货运
题目描述
Upstairs 得到了一家货运公司,准备开始运营。
地图是一棵有 个节点的树,节点编号为 ,根节点为 。每个节点有一个仓库,第 个仓库中有非负整数 单位的物资。
现在要把所有物资运到根节点的仓库。每条边每天最多通过 单位物资,不同边可以同时运输;物资沿一条边运输需要一天,到达节点后可以在之后的日子继续运输。
求将所有物资运到根节点的最少天数。根节点原有的物资无需运输。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示这两个节点之间有一条双向边。
接下来 行,每行一个非负整数 ,表示第 个仓库的物资数量。
输出格式
输出一个整数,表示最少天数。
样例输入1
3 2
1 2
2 3
1
2
1
样例输出1
1
样例输入2
5 1
1 2
2 3
2 4
2 5
5
1
2
2
1
样例输出2
6
样例说明
第一例中根节点为 ,节点 和节点 可以同时用一天把各自的一单位物资运到根节点。
数据范围
| 测试点 | 附加限制 |
|---|---|
| 1—2 | |
| 3—4 | |
| 5 | ,深度相同的所有节点总共最多有 单位物资 |
| 6—10 |
所有数据的答案都在有符号 位整数范围内。