题目描述

有 $n$ 个农民，他们住在 $n$ 个不同的村子里，这 $n$ 个村子形成一棵树，每个农民初始时有 $x$ 元钱。
每一次操作，一个农民可以从它自己的钱中，取出任意数量的钱，交给某个相邻村子的农民。
对于每个农民给定一个值 $v_i$，求最少需要多少次操作，使得每个农民最终拿到的钱 $\geq$ 给定的值。

输入格式

第一行包含一个整数 $n$ ，即农民数。
第二行包含一个整数 $x$ ，即每个农民初始时拥有的钱数。
第三行包含 $n$ 个整数，第 $i$ 个数表示 $v_i$ 。
接下来 $n-1$ 行每行包含两个整数, 表示树上的一条边。

输出格式

输出一行一个整数, 即最少需要的操作次数。

6
15
10 20 18 16 6 16
1 4
4 5
4 6
6 2
5 3

5

提示

对于 $100\%$ 的数据，$1 \leq n \leq 2000,~0 \leq x \leq 10000,~\sum\limits_{i=1}^{n}v_i \leq n\times x$