Problem 4161 --试题 G: 生产车间

4161: 试题 G: 生产车间

$0.00\%$ 下一题

Description

小明正在改造一个生产车间的生产流水线。这个车间共有 n 台设备，构成

以 1 为根结点的一棵树，结点 i 有权值 wi。其中叶节点的权值 wi 表示每单位时

间将产出 wi 单位的材料并送往父结点，根结点的权值 wi 表示每单位时间内能

打包多少单位成品，其他结点的权值 wi 表示每单位时间最多能加工 wi 单位的

材料并送往父结点。

由于当前生产线中某些结点存在产能不够的问题导致生产线无法正常运行，

即存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限。小明

计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结

点每单位时间内最多能打包多少单位的成品？

输入共 n + 1 行。

第一行为一个正整数 n。

第二行为 n 个由空格分开的正整数 w1,w2, ...,wn。

后面 n − 1 行，每行两个整数表示树上的一条边连接的两个结点。

输出共一行，一个整数代表答案。

9
9 7 3 7 1 6 2 2 7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
6 9

【样例说明】

删掉结点 4、9 后生产线满足条件，根结点 1 每单位时间将打包出 8 单位

的成品。

【评测用例规模与约定】

对于 20% 的评测用例，2 ≤ n ≤ 100。

对于 100% 的评测用例，2 ≤ n ≤ 1000，wi ≤ 1000。

竞赛编号	竞赛名称	竞赛时间	访问比赛