레이팅 미적용Krešo went to a local family farm and bought a bunch of hot peppers that are neatly connected with pieces
of string into a so-called wreath. In this task, a wreath consists of \(n\) peppers and (\(n - 1\)) pieces of string.
Each piece of string connects two different peppers, and each two peppers in the wreath are connected
(directly or indirectly) by the string. Therefore, the peppers and pieces of string form a so-called tree.
Making one cut with scissors, Krešo can cut the string, and split a pepper wreath into two smaller wreaths,
which can again be split into smaller wreaths, and so on. Notice that a single pepper not connected to
anything also forms a wreath.
Figure 1: The initial wreaths from the first two test cases together with the optimal cuts.
The spiciness of a single peper is measured using the so-called Scoville scale, and is represented as a
non-negative integer. The spiciness of the wreath is the sum of spiciness of individual peppers it contains.
Krešo wants to spice up the lunch of high school students after an informatics competition and knows
that the average high school student can eat a wreath whose spiciness is at most \(k\) before they need to
ask for a doctor and a juvenile lawyer.
Determine the minimal number of cuts needed so that Krešo can split the initial wreath into wreaths with
spiciness at most \(k\).
In all subtasks, it holds \(n \ge 2\) i \(0 \le h_{1}\), h_{2}, . . . , \(h_{n} \le k \le 3\,000\,000\).
Subtask Score Constraints
1
11
\(n \le 15\)
2
13
\(n \le 100\,000\), each pepper \(x = 1\), . . . , \(n - 1\) is connected to pepper \(x + 1\).
3
27
\(n \le 1\,000\)
4
49
\(n \le 100\,000\)
The first line of input contains the integers \(n\) and \(k\) — the number of peppers and the maximal allowed
spiciness of an individual wreath. The peppers are denoted with numbers from 1 to \(n\). The following line
contains \(n\) integers h1, h2, . . . , hn — the number \(hj\) is the spiciness of pepper \(j\). Each of the following
\(n - 1\) lines contains two distinct integers \(x\) and \(y\) (\(1 \le x\), \(y \le n\)) — the labels of the peppers directly
connected with a piece of string in the initial wreath. The peppers and strings form a tree, as described
in the task.
You must output the minimal number of cuts.
5 5
1 2 3 4 5
1 2
2 3
3 4
4 5
3
10 10
3 4 2 3 7 1 4 1 5 2
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
3
6 9
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6
2