【BZOJ2525】[Poi2011]Dynamite
Description
Byteotian Cave的结构是一棵N个节点的树，其中某些点上面已经安置了炸.药，现在需要点燃M个点上的引线引爆所有的炸.药。
某个点上的引线被点燃后的1单位时间内，在树上和它相邻的点的引线会被点燃。如果一个有炸.药的点的引信被点燃，那么这个点上的炸.药会爆炸。
求引爆所有炸.药的最短时间。
输入：
第一行是两个整数N,M。(1<=m<=n<=300000）
接下来一行有N个整数Di，第I个数为1表示该点有炸.药。
接下来N-1行每行有两个数A,B，表示A和B之间有一条边。
输出：
最短时间。
样例解释：
点燃3,5上的引线。 Sample Input
7 2
1 0 1 1 0 1 1
1 3
2 3
3 4
4 5
5 6
5 7
1 0 1 1 0 1 1
1 3
2 3
3 4
4 5
5 6
5 7
Sample Output
1
/*
二分答案。
然后接下来从下往上扫整棵树。
节点的状态有：
第一种 子树内没有不被覆盖的关键点，并且子树中有一个节点的贡献可以继续往上。
第二种 子树内有不被覆盖的关键点，子树中没有节点的贡献可以继续往上。
第三种 既没有 不被覆盖的关键点，又没有 可以继续往上贡献的点。
第四种 都有。
但是 可以证明，第四种情况存在的话，显然可以在子树外挑一个点来覆盖没有被覆盖的关键点，但是这个时候子树内的挑选的点就没有卵用了，所以这种情况可以归到第三种。
然后具体就是贪心讨论的过程了。
贪心的思想就是，能不染就不染
显然第一种需要记录还能往上走多少。
第二种需要记录最远的不被覆盖的关键点到达目前的根节点的距离
*/#include<iostream>
#include<cstdio>#define N 300007using namespace std;
int n,m,h[N],cnt,d[N],sum,sm,mx[N],mn[N];
struct edge
{int ne,to;
}e[N<<1];inline int read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}void add(int u,int v)
{ e[++cnt].to=v;e[cnt].ne=h[u];h[u]=cnt;
}void dfs(int u,int fa,int w)
{mx[u]=-1e9,mn[u]=1e9;for(int i=h[u];i;i=e[i].ne)if(e[i].to!=fa){dfs(e[i].to,u,w);mx[u]=max(mx[u],mx[e[i].to]+1);mn[u]=min(mn[u],mn[e[i].to]+1);}if(d[u]&&mn[u]>w) mx[u]=max(mx[u],0);if(mx[u]+mn[u]<=w)mx[u]=-1e9;if(mx[u]==w) sm++,mx[u]=-1e9,mn[u]=0;
}bool ok(int w)
{sm=0;dfs(1,0,w);return sm+(mx[1]>=0)<=m;
}int main()
{n=read(),m=read();for(int i=1;i<=n;i++)d[i]=read(),sum+=d[i];for(int i=1;i<n;i++){int x=read(),y=read();add(x,y),add(y,x);}if(sum<=m){puts("0");return 0;}int l=0,r=n,ans=n;while(l<=r){int mid=(l+r)>>1;if(ok(mid)) r=mid-1,ans=mid;else l=mid+1;}printf("%d\n",ans);return 0;
}