生产车间
题号：NC307649
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小明正在改造一个生产车间的生产流水线。这个车间共有 n 台设备，构成以 1 为根结点的一棵树，结点 i 有权值 w_i。其中叶节点的权值 w_i 表示每单位时间将产出 w_i 单位的材料并送往父结点，根结点的权值 w_i 表示每单位时间内能打包多少单位成品，其他结点的权值 w_i 表示每单位时间最多能加工 w_i 单位的材料并送往父结点。

由于当前生产线中某些结点存在产能不够的问题导致生产线无法正常运行，即存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限。小明计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结点每单位时间内最多能打包多少单位的成品？

输入描述:

输入共 n + 1 行。

第一行为一个正整数 n。

第二行为 n 个由空格分开的正整数 w_1,w_2, \dots,w_n。

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

- 对于 100\% 的评测用例，2 \leq n \leq 1000，1\leq w_i \leq 1000。

输出描述:

输出共一行，一个整数代表答案。
示例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

输出

复制 
8

说明

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