以下题面由 AI 翻译。

题目描述

Byteotian 洞穴由 $n$ 个洞室和 $n-1$ 条连接它们的走廊构成。每对洞室之间都有一条唯一的路径。

某些洞室中装有炸药。

每条走廊中都铺设了引线。每个洞室中相邻走廊的引线交汇于一点，如果该洞室中有炸药，则引线会连接到炸药上。相邻两个洞室之间的引线燃烧需要恰好一个单位时间，炸药在火焰到达其所在洞室的瞬间爆炸。

我们需要在 $m$ 个洞室中点燃引线（在引线的交汇点），使得所有炸药爆炸的时间尽可能短。请编写程序确定这个最短时间。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示洞室数量和允许点燃引线的洞室数量。洞室编号为 $1$ 到 $n$。

第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$，表示各洞室是否有炸药（$1$ 表示有，$0$ 表示无）。

接下来 $n-1$ 行描述洞穴的走廊，每行两个整数 $a, b$，表示洞室 $a$ 和 $b$ 之间有走廊。

输出格式

输出一行，表示所有炸药爆炸的最短时间。

样例数据

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

1

数据范围

• 对于 $10\%$ 的数据，$n \leq 10$。
• 对于 $40\%$ 的数据，$n \leq 10^3$。
• 对于 $100\%$ 的数据，$1 \leq m \leq n \leq 3 \times 10^5$，$d_i \in \{0, 1\}$，$1 \leq a < b \leq n$。

提示

问题转化：在树上选择 $m$ 个点燃点，使得所有关键节点（有炸药的洞室）到最近点燃点的距离的最大值最小。该问题可以通过二分答案结合贪心算法解决。