题目描述

有 $n$ 个农民，他们住在 $n$ 个不同的村子里。这 $n$ 个村子形成一棵树。

每个农民初始时获得 $x$ 的钱。

每一次操作，一个农民可以从它自己的钱中，取出任意数量的钱，交给某个相邻村子的农民。

对于每个农民给定一个值 $v_i$，求最少需要多少次操作，使得每个农民最终拿到的钱大于等于给定的值。

输入格式

第 $1$ 行一个整数 $n$。

第 $2$ 行一个整数 $x$。

第 $3$ 行 $n$ 个整数，表示 $v_i$。保证所有 $v_i$ 的和 $\le n \times x$。

第 $4$ 到 $n+2$ 行每行两个 $1$ 到 $n$ 的数，表示树上的一条边。边是双向的。

输出格式

一行一个整数，最少需要的操作次数。

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

5

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 2 \times 10^3$，$0\le x\le 10^4$。