Description

CFF 山洞由n个洞穴和连接这些洞穴的n-1条过道组成。对于每一对洞穴，从一个洞穴到达另一个都有唯一的路径，并且不需要离开山洞。炸药放在了某些山洞中。每条过道都放了引线。在每个洞穴中，相邻过道的引线交于一点，如果洞穴中有炸药，那么它们会与炸药相连。相邻两个洞穴之间的引线燃尽都恰好需要一单位时间。并且只要火传到了有炸药的洞穴中，炸药就会立即爆炸。

我们希望点燃m个洞穴的引线（在引线的交点处点燃），使得引线引燃后，所有炸药在最短时间内爆炸。写一个程序求出这个最小可能时间。

Input Format

第一行包含两个整数n,m，分别表示山洞中洞穴的个数和可以点火的引线数；

接下来一行n个整数d_i，如果d_i=1则1号山洞中有炸药，如果d_i=0则没有。

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

Output Format

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

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

1

Hint

【样例解释】

我们可以点燃洞穴中3,5的引线。洞穴3的炸药在时间0时被引爆，洞穴1,4,6,7内的炸药都在一单位之间后被引爆。

【数据范围】

对于所有数据，1≤m≤n≤3×10^5，d_i∈{0,1}，1≤a<b≤n；

对于10%的分数，n≤10；

对于40%的分数，n≤10^3。

Source

POI 2011改编题目