题目描述

小明正在改造一个生产车间的生产流水线。这个车间共有 $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$ 行，每行两个整数表示树上的一条边连接的两个结点。

输出格式

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

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$ 单位的成品。

评测用例规模与约定

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