题目描述

有 $n$ 个农民，他们住在 $n$ 个不同的村子里，这 $n$ 个村子形成一棵树，每个农民初始时有 $x$ 元钱。

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

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

输入格式

第一行包含一个整数 $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\le n\le 2000$，$0\le x\le 10000$，$\sum\limits_{i=1}^n v_i\le n\times x$。

说明

翻译自 Croatian Highschool Competitions In Informatics 2009 Final Exam #1 T2 PODJELA。