9445: CFF炸药
内存限制:256 MB
时间限制:1.000 S
提交:4
解决:0
评测方式:文本比较
命题人:
题目描述
CFF 山洞由n个洞穴和连接这些洞穴的n-1条过道组成。对于每一对洞穴,从一个洞穴到达另一个都有唯一的路径,并且不需要离开山洞。炸药放在了某些山洞中。每条过道都放了引线。在每个洞穴中,相邻过道的引线交于一点,如果洞穴中有炸药,那么它们会与炸药相连。相邻两个洞穴之间的引线燃尽都恰好需要一单位时间。并且只要火传到了有炸药的洞穴中,炸药就会立即爆炸。
我们希望点燃m个洞穴的引线(在引线的交点处点燃),使得引线引燃后,所有炸药在最短时间内爆炸。写一个程序求出这个最小可能时间。
输入
第一行包含两个整数n,m,分别表示山洞中洞穴的个数和可以点火的引线数;
接下来一行n个整数d~i~,如果d~i~=1则1号山洞中有炸药,如果d~i~=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