P16189 [COI 2018] Paprike 胡椒

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$ 的两个辣椒之间用绳子直接相连。辣椒和绳子构成一棵树。

输出最少需要剪的刀数。

### 数据范围 所有子任务中，满足 $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。