Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

题面翻译

Krešo 去了当地的一个家庭农场,买了一堆辣椒,这些辣椒被整齐地连接在一起 串成所谓的花环。 在这个任务中,一个花环由 n 个辣椒和 (n-1) 根绳子组成。 每根绳子连接两个不同的辣椒,花环中的每两个辣椒都连接在一起 (直接或间接)由字符串。 因此,辣椒和串串形成一棵所谓的树。 用剪刀剪一个,Krešo 可以剪断绳子,把一个胡椒花环分成两个更小的花环, 它可以再次分成更小的花环,依此类推。 请注意,单个辣椒未连接到 任何东西也可以形成一个花圈。

12.png

图 1:前两个测试用例的初始花环以及最佳切割。

使用所谓的斯科维尔量表测量单个辣椒的辣度,并表示为 非负整数。 花圈的辣味是它所含的单个辣椒辣味的总和。 Krešo 想在信息学竞赛后为高中生的午餐增添趣味,他知道 一个普通的高中生可以在他们需要之前吃一个辣度最多为k的花环 要求医生和少年律师。 确定所需的最小切割次数,以便 Krešo 可以将初始花环分成具有 辣度至多k。

题目描述

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.

12.png

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.

Input

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 ≤ x, y ≤ 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.

输入的第一行包含整数 n 和 k——辣椒的数量和允许的最大值 单个花环的辣味。 辣椒用从 1 到 n 的数字表示。 以下行 包含 n 个整数 h1, h2, . . . , hn——hj 为辣椒 j 的辣度。 以下各项 n − 1 行包含两个不同的整数 x 和 y (1 ≤ x, y ≤ n) — 直接是辣椒的标签 在最初的花环上用一根绳子连接起来。 如上所述,辣椒和细绳形成一棵树 在任务中。

Output

You must output the minimal number of cuts.

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #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

样例输出 #2

3

样例 #3

样例输入 #3

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

样例输出 #3

2

Scoring

In all subtasks, it holds n ≥ 2 i 0 ≤ h1, h2, . . . , hn ≤ k ≤ 3 000 000.

13.png