Description：

$N$ 个节点的树，某些点安置了炸药，点燃 $M$ 个点上的引线引爆所有的炸药。某个点上的引线被点燃后的 $1$ 单位时间内，在树上和它相邻的点的引线会被点燃。如果一个有炸药的点的引信被点燃，那么这个点上的炸药会爆炸。

求引爆所有炸药的最短时间。

$1\le m,n \le 300000$

Solution：

先二分一个时间，问题就变成了能否点燃 $\le$ 个点使得在规定时间内把整棵树中的重要点点燃，一个直观的想法是像消防局的设立一样，把所有点按深度从大到小排序一个个考虑，每次找到最靠上的能点燃它的祖先点燃，把所有距离在范围内的点都标记。但这题距离最大可能会达到 $O(n)$ 级别，所以不能暴力标记。

贪心的思路不变，考虑如何优化点燃的过程，对于每一个子树，有三种状态：

$1$ 、子树中存在未被点燃的关键点，最大深度为 $dep$ 。

$2$ 、子树中不存在未被点燃的关键点，且还可以向上点燃 $len$ 的距离。

$3$ 、子树中的关键点都被点燃了，也不能向上点燃。

在考虑当前这个点时分别记录子树中最深的未被点燃的点的深度和最长可以向上点燃的距离分类讨论，如果 $maxdep=mid$ ，就在这个点新点燃一个，最后如果根节点状态是 $1$ ，那还要加一。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

bool tag[MAXN];

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

bool vis[MAXN];

#define fi first

#define se second

#define INF 0x3f3f3f3f

int cnt = 0;

pair<int,int> dp(int k,int s)

{

	vis[k] = true;

	int maxlen = -INF,maxdep = 0;

	if(!tag[k])maxdep = -INF;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		pair<int,int> res = dp(e[i].to,s);

		if(res.fi == 2)continue;

		if(res.fi == 1)maxlen = max(maxlen,res.se - 1);

		if(res.fi == 0)maxdep = max(maxdep,res.se + 1);

	}

	if(maxlen >= maxdep)return make_pair(1,maxlen);

	else if(maxdep == s)

	{

		++cnt;

		return make_pair(1,s);

	}

	else if(maxlen == 0 && maxdep == 0)return make_pair(2,0);

	else return make_pair(0,maxdep);

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

    scanf("%d%d",&n,&m);

    int k;

    memset(tag,false,sizeof(tag));

    for(int i = 1;i <= n;++i)

    {

        k = read();

        tag[i] = (k == 1);

    }

    int a,b;

    for(int i = 1;i < n;++i)

    {

        a = read();b = read();

        add(a,b);

    }

    int l = 0,r = n,mid;

    while(l < r)

    {

        mid = ((l + r) >> 1);

        cnt = 0;

        memset(vis,false,sizeof(vis));

        if(dp(1,mid).fi == 0)++cnt;

        if(cnt <= m)r = mid;

        else l = mid + 1;

    }

    cout << l << endl;

    return 0;

}