Byteotian Cave的结构是一棵N个节点的树，其中某些点上面已经安置了烟火，现在需要点燃M个点上的引线引爆所
有的烟火。某个点上的引线被点燃后的1单位时间内，在树上和它相邻的点的引线会被点燃。如果一个有烟火的点
的引信被点燃，那么这个点上的烟火会爆炸。求引爆所有烟火的最短时间。
1<=m<=n<=300000
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
可以发现实际上要求的就是选择点到所有烟火点的最大距离最小，这个可以二分答案，然后我就不会做了
一个说法是：如果选择的代价相等那么就是贪心，如果选择代价不等那么就是dp
二分最短时间,求出最小的需要引爆数
至于关键点的引爆状态有关
f[i] 以i为根的子树中已经引爆的点离i最近的距离
g[i] 以i为根的子树中未引爆的点离i最远的距离
回溯到每个节点时，优先考虑用另一个儿子中的点覆盖其他儿子
if(f[i]+g[i]<=mid) g[i]=INF
if(g[i]==mid) 必须引爆x
#include <iostream> #include <cstdio> #include <cstring> #define INF 1000000000 #define maxn 300005 using namespace std; int n,m; int a[maxn]; int ans; struct edge { int to,ne; }b[maxn*2]; int k=0,head[maxn]; int f[maxn],g[maxn]; int limit; int num=0,op1=0; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } void add(int u,int v) { k++; b[k].to=v; b[k].ne=head[u]; head[u]=k; } void dfs(int x,int pre) { f[x]=INF; if(a[x]) g[x]=0; else g[x]=-INF; for(int i=head[x];i!=-1;i=b[i].ne) if(b[i].to!=pre) { dfs(b[i].to,x); f[x]=min(f[x],f[b[i].to]+1); g[x]=max(g[x],g[b[i].to]+1); } if(g[x]+f[x]<=limit) g[x]=-INF; if(g[x]==limit){ f[x]=0,g[x]=-INF,num++; } } bool check(int x) { if(!x) return op1<=m; limit=x; num=0; dfs(1,0); if(g[1]+f[1]>limit) num++; return num<=m; } void getans() { int l=0,r=n,mid; ans=n; while(l<=r){ mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } } int main() { memset(head,-1,sizeof(head)); n=read(); m=read(); for(int i=1;i<=n;i++){ a[i]=read(); if(a[i]) op1++; } int x,y; for(int i=1;i<n;i++) { x=read(); y=read(); add(x,y); add(y,x); } getans(); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/cutemush/p/11696978.html