#P7394. [2019雅礼集训]货运

    ID: 7408 传统题 2000ms 500MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>难度分类提高贪心排序贪心枚举与搜索深度优先搜索CF2100

[2019雅礼集训]货运

货运

题目描述

Upstairs 得到了一家货运公司,准备开始运营。

地图是一棵有 nn 个节点的树,节点编号为 1,…,n1,\ldots,n,根节点为 ss。每个节点有一个仓库,第 ii 个仓库中有非负整数 aia_i 单位的物资。

现在要把所有物资运到根节点的仓库。每条边每天最多通过 11 单位物资,不同边可以同时运输;物资沿一条边运输需要一天,到达节点后可以在之后的日子继续运输。

求将所有物资运到根节点的最少天数。根节点原有的物资无需运输。

输入格式

第一行两个整数 n,sn,s。

接下来 n−1n-1 行,每行两个整数 x,yx,y,表示这两个节点之间有一条双向边。

接下来 nn 行,每行一个非负整数 aia_i,表示第 ii 个仓库的物资数量。

输出格式

输出一个整数,表示最少天数。

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

样例说明

第一例中根节点为 22,节点 11 和节点 33 可以同时用一天把各自的一单位物资运到根节点。

数据范围

测试点 附加限制
1—2 1≤n≤101\le n\le10
3—4 1≤n≤10001\le n\le1000
5 1≤n≤1051\le n\le10^5,深度相同的所有节点总共最多有 11 单位物资
6—10 1≤n≤1051\le n\le10^5

所有数据的答案都在有符号 3232 位整数范围内。