Problem D: 太空供水

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

空间站各舱室呈树状分布，一共有N个舱室，使用管道相连。经过统计得到了哪些太空舱现在有用水需求，目前需要给这些有需求的太空舱通水，但是初始只能在其中M个舱室安装水源。如果一个太空舱获得了水源，那么与它相连的太空舱可以花费1时间单位通过管道也获得水源。现在小明需要找出安装初始水源位置，使得在最短时间内，所有有用水需求的太空舱都可以获得水源。

Input

第一行是两个整数N,M。(1≤M≤N≤300000）

接下来一行有N个整数0和1，其中第i个数为1表示编号为i的舱室有用水需求。

接下来N-1行每行有两个数A,B，表示A和B之间有一条管道相连。

Output

一个整数， 表示使所有有用水需求的太空舱得到供水的最短时间。

Sample Input复制

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

Sample Output复制

1