P6223 [CHCI 2009 Final Exam #1] PODJELA

There are $n$ farmers living in $n$ different villages. These $n$ villages form a tree. Initially, each farmer has $x$ dollars. In one operation, a farmer may take any amount of money from their own money and give it to a farmer in an adjacent village. For each farmer, a value $v_i$ is given. Find the minimum number of operations needed so that in the end every farmer has money $\ge$ the given value.

The first line contains an integer $n$, the number of farmers. The second line contains an integer $x$, the amount of money each farmer initially has. The third line contains $n$ integers, where the $i$-th number is $v_i$. The next $n - 1$ lines each contain two integers, representing an edge of the tree.

Output one line with one integer, the minimum number of operations required.

#### Constraints For $100\%$ of the testdata, $1 \le n \le 2000$, $0 \le x \le 10000$, $\sum\limits_{i=1}^n v_i \le n \times x$. #### Notes Translated from [Croatian Highschool Competitions In Informatics 2009 Final Exam #1 T2 PODJELA](https://hsin.hr/2009/final/first_day/tasks.pdf)。 Translated by ChatGPT 5