题目背景

1s，1024MB。

题目描述

Krešo 去了当地的家庭农场，买了一串辣椒，这串辣椒用绳子一根根串起来，形成了一个“花环”。这个花环由 $n$ 个辣椒和 $(n − 1)$ 根绳子组成。每根绳子连接两个不同的辣椒，且花环中任意两个辣椒之间都能通过绳子直接或间接连通。也就是说，这些辣椒和绳子构成了一棵树。Krešo 用剪刀剪一刀，就能把绳子剪断，将一个花环分成两个更小的花环，这些小花环还能继续被分割，依此类推。注意，一个单独的辣椒（没有连接任何绳子）也算是一个花环。

图1：前两个测试样例中的初始花环及其最优剪切方案。

每个辣椒的辣度用著名的斯科维尔辣度指数（Scoville scale）表示，是一个非负整数。一个花环的辣度是它包含的所有辣椒辣度之和。Krešo 想给参加信息学竞赛的高中生们准备午餐，他知道普通高中生最多能吃辣度不超过 $k$ 的花环，超过这个辣度就得叫医生和未成年律师了。

请你帮忙计算，最少需要剪多少刀，才能把初始花环分成辣度都不超过 $k$ 的若干个花环。

输入格式

第一行输入两个整数 $n$ 和 $k$，分别表示辣椒的数量和单个花环允许的最大辣度。辣椒编号从 $1$ 到 $n$。第二行输入 $n$ 个整数 $h_1, h_2, \ldots, h_n$，其中 $h_j$ 表示编号为 $j$ 的辣椒的辣度。接下来 $n − 1$ 行，每行两个不同的整数 $x$ 和 $y\ (1 \le x, y \le n)$，表示初始花环中编号为 $x$ 和 $y$ 的两个辣椒之间用绳子直接相连。辣椒和绳子构成一棵树。

输出格式

输出最少需要剪的刀数。

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

提示

数据范围

所有子任务中，满足 $n \ge 2$ 且 $0 \le h_1, h_2, \ldots, h_n \le k \le 3\,000\,000$。

子任务

::cute-table{three} |编号 |分值 |限制条件 | |:-:|:--:|:--------:| |$1$|$11$|$n\le15$ | |$2$|$13$|$n \le 100\,000$，且辣椒 $x = 1, ..., n − 1$ 依次连接到辣椒 $x + 1$。| |$3$|$27$|$n \le 1\,000$| |$4$|$49$|$n \le 1\,000\,000$|

翻译来源：GPT 4.1 mini。