题目描述

CFF 山洞由 $n$ 个洞穴和连接这些洞穴的 $n-1$ 条过道组成。对于每一对洞穴，从一个洞穴到达另一个都有唯一的路径，并且不需要离开山洞。也就是说，山洞的结构是一棵树。

某些洞穴中放置了炸药。每条过道中都放了引线。在每个洞穴中，相邻过道的引线交于一点，如果该洞穴中有炸药，那么引线会与炸药相连。任意相邻两个洞穴之间的引线燃尽都恰好需要一单位时间。一旦火传到有炸药的洞穴，炸药会立即爆炸。

现在我们可以在 $m$ 个洞穴的引线交点处同时点火。希望引线引燃后，所有炸药在尽可能短的时间内全部爆炸。请你编写一个程序，求出这个最小可能时间。

输入格式

第一行包含两个整数 $n, m$，分别表示山洞中洞穴的个数和允许点火的洞穴数量。

第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$，$d_i$ 为 $1$ 表示第 $i$ 个洞穴中有炸药，$d_i$ 为 $0$ 表示没有。

接下来 $n-1$ 行，每行两个整数 $a, b$，表示一条过道连接洞穴 $a$ 和洞穴 $b$。

输出格式

一行一个整数，表示引爆所有炸药所需的最短时间。

样例

7 2
1 0 1 1 0 1 1
1 2
2 3
3 4
4 5
5 6
6 7

1

样例解释：
山洞结构是一条链 $1 - 2 - 3 - 4 - 5 - 6 - 7$，其中洞穴 $1, 3, 4, 6, 7$ 有炸药。可以点火 $m=2$ 个洞穴。
一种最优方案是在洞穴 $3$ 和洞穴 $5$ 点火：

• 洞穴 $3$ 的炸药在时间 $0$ 时直接引爆。
• 火从洞穴 $3$ 沿过道向两边传播：$1$ 单位时间后到达洞穴 $2$ 和 $4$，引爆洞穴 $4$ 的炸药，同时火从洞穴 $5$ 向两边传播引爆洞穴 $6$ 等。
• 所有炸药在时间 $1$ 后全部引爆。
  可以证明无法在更短时间内引爆所有炸药，因此答案是 $1$。

数据范围

• 对于所有数据：$1 \le m \le n \le 3 \times 10^5$，$d_i \in \{0, 1\}$，$1 \le a, b \le n$
• 对于 $10\%$ 的分数：$n \le 10$
• 对于 $40\%$ 的分数：$n \le 10^3$

来源

POI 2011 改编题目