P3523 [POI 2011] DYN-Dynamite

Byteotian 洞穴由 $n$ 个房间和连接它们的 $n-1$ 条走廊组成。对于每一对房间，有一条唯一的路径可以在不离开洞穴的情况下从一个房间移动到另一个房间。 某些房间中设置了炸药。 每条走廊上都铺设了导火索。 在每个房间中，相邻走廊的导火索在一个点相遇，并进一步连接到房间内的炸药（如果房间内有炸药）。导火索在两个相邻房间之间燃烧需要恰好一个时间单位，当火焰到达房间时，房间内的炸药立即爆炸。 我们希望在 $m$ 个房间（导火索的连接点）点燃导火索，使得所有炸药在点燃导火索后以最短的时间爆炸。编写一个程序来确定可能的最短时间。

标准输入的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 300\ 000$），用一个空格分隔，分别表示洞穴中的房间数量和可以点燃导火索的房间数量。 房间编号从 1 到 $n$。 下一行包含 $n$ 个整数 $d_1,d_2,\cdots,d_n$（$d_i \in \{0,1\}$），用空格分隔。 如果 $d_i=1$，则第 $i$ 个房间中有炸药，如果 $d_i=0$，则没有。接下来的 $n-1$ 行指定了洞穴的走廊。每行包含两个整数 $a,b$（$1 \le a < b \le n$），用空格分隔，表示有一条走廊连接房间 $a$ 和 $b$。每条走廊在描述中恰好出现一次。 你可以假设在价值 10% 的测试中，额外条件是 $n \le 10$，而在价值 40% 的测试中，额外条件是 $n \le 1\ 000$。

标准输出的第一行应包含一个整数，表示从点燃导火索到所有炸药爆炸所需的最短时间。

题面翻译由 ChatGPT-4o 提供。