COI '17 #1 Paprike

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

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 pepper 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.

Input Specification

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 h_1, h_2, \dots, h_n — the number h_j 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.

Output Specification

You must output the minimal number of cuts.

Constraints

For all subtasks:

n \ge 2

0 \le h_1, h_2, \dots, h_n \le k \le 3\,000\,000

SubtaskPointsConstraints
111n \le 15
213n \le 100\,000, each pepper x = 1, \dots, n-1 is connected to pepper x+1.
327n \le 1\,000
449n \le 100\,000

Sample Input 1

5 5
1 2 3 4 5
1 2
2 3
3 4
4 5

Sample Output 1

3

Sample Input 2

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

Sample Output 2

3

Sample Input 3

6 9
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6

Sample Output 3

2

Comments

There are no comments at the moment.