P16189 [COI 2018] Paprike Pepper

1 s, 1024 MB.

Krešo went to a local family farm and bought a string of peppers. The peppers are tied one by one with strings to form a “wreath”. This wreath consists of $n$ peppers and $(n - 1)$ strings. Each string connects two different peppers, and any two peppers in the wreath are connected directly or indirectly through strings. In other words, these peppers and strings form a tree. With one cut of scissors, Krešo can cut a string and split one wreath into two smaller wreaths. These smaller wreaths can then be split further, and so on. Note that a single pepper (with no strings connected) is also considered a wreath.  Figure 1: The initial wreaths in the first two sample tests and their optimal cutting plans. Each pepper’s spiciness is given by the famous Scoville scale, and is a non-negative integer. The spiciness of a wreath is the sum of the spiciness values of all peppers in it. Krešo wants to prepare lunch for high school students participating in informatics competitions. He knows that an average high school student can eat at most a wreath with spiciness not exceeding $k$. If the spiciness is greater than $k$, he would have to call a doctor and a minor’s lawyer. Please compute the minimum number of cuts needed to split the initial wreath into several wreaths, each with spiciness at most $k$.

The first line contains two integers $n$ and $k$, representing the number of peppers and the maximum allowed spiciness of a single wreath. The peppers are numbered from $1$ to $n$. The second line contains $n$ integers $h_1, h_2, \ldots, h_n$, where $h_j$ is the spiciness of pepper $j$. The next $n - 1$ lines each contain two different integers $x$ and $y\ (1 \le x, y \le n)$, indicating that peppers $x$ and $y$ are directly connected by a string in the initial wreath. The peppers and strings form a tree.

Output the minimum number of cuts required.

### Constraints In all subtasks, it holds that $n \ge 2$ and $0 \le h_1, h_2, \ldots, h_n \le k \le 3\,000\,000$. ### Subtasks ::cute-table{three} |ID |Score |Constraints | |:-:|:--:|:--------:| |$1$|$11$|$n \le 15$| |$2$|$13$|$n \le 100\,000$, and peppers $x = 1, ..., n - 1$ are connected in order to pepper $x + 1$.| |$3$|$27$|$n \le 1\,000$| |$4$|$49$|$n \le 1\,000\,000$| Translation source: GPT 4.1 mini. Translated by ChatGPT 5