题意：

给出一颗n个结点的树，上面有若干个关键结点；

现在可以在这些结点上选最多m个点，求最小化关键点到选择点的最大距离；

题解：

首先这道题是一个最大最小化的问题，很容易想到二分；
二分一个数L表示答案的；
然后问题就转化成了一个判定性问题：判定能否用m个点覆盖整个树上的关键点；
判定过程是贪心的；
设dis[x]为x的子树中最近的选择的点的距离，g[x]为x的子树中最远的未覆盖的关键点的距离；
我们在深搜的过程中维护这两个东西；
当dis[x]+g[x]>mid时，说明x子树的点不能覆盖它子树的所有关键点了，这是我们就要考虑再选择一个点来覆盖树；

我们贪心的考虑的话，如果选择这个点的父亲能覆盖这个点，那么我们就让父亲来覆盖；

也就是只有满足g[x]>mid的时候，我们才新选择一个点；

这样的贪心是正确的，在二分判断的时候判断建的点是否<=m就可以了；

时间复杂度O(nlogn)，似乎有些卡但是不太卡时；

代码：

#include<cctype>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 310000
#define LEN 1<<16
using namespace std;
typedef long long ll;
int next[N<<1],to[N<<1],head[N],ce;
int dis[N],g[N],cnt,mid;
bool a[N],is[N];
void add(int x,int y)
{to[++ce]=y;next[ce]=head[x];head[x]=ce;
}
char getc()
{static char *S,*T,buf[LEN];if(S==T){T=(S=buf)+fread(buf,1,LEN,stdin);if(S==T)return EOF;}return *S++;
}
int read()
{static char ch;static int D;while(!isdigit(ch=getc()));for(D=ch-'0';isdigit(ch=getc());)D=D*10+ch-'0';return D;
}
void dfs(int x,int pre)
{g[x]=-0x3f3f3f3f;dis[x]=0x3f3f3f3f;is[x]=0;for(int i=head[x];i;i=next[i]){if(to[i]!=pre){dfs(to[i],x);dis[x]=min(dis[x],dis[to[i]]+1);g[x]=max(g[x],g[to[i]]+1);is[x]=1;}}if(a[x])g[x]=max(g[x],0);if(!is[x]){dis[x]=mid+1;}if(dis[x]+g[x]>mid&&g[x]+1>mid){cnt++;dis[x]=0;g[x]=-0x3f3f3f3f;}if(dis[x]+g[x]<=mid){g[x]=-0x3f3f3f3f;}
}
int main()
{int n,m,i,j,k,x,y,l,r;n=read(),m=read();for(i=1;i<=n;i++)a[i]=read();for(i=1;i<n;i++){x=read(),y=read();add(x,y),add(y,x);}l=0,r=n-1;while(l<=r){mid=l+r>>1;cnt=0;dfs(1,0);if(cnt<m||(cnt==m&&dis[1]+g[1]<=mid))r=mid-1;elsel=mid+1;}printf("%d\n",l);return 0;
}