D61 树的直径 二分 P3000 [USACO10DEC] Cow Calisthenics G

// 树的直径 二分 O(nlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int ne[N<<1],to[N<<1],h[N],idx;
void add(int a,int b){
  to[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
int n,s,cnt,len,d[N]; //d[x]表示节点x下面悬挂的合法的最长链

void dfs(int x,int fa){
  if(cnt>s) return; //剪枝
  for(int i=h[x],y;i;i=ne[i])if((y=to[i])!=fa){
    dfs(y,x);
    if(d[x]+d[y]+1<=len)d[x]=max(d[x],d[y]+1); //两个链长和不超过len，取长链长度
    else ++cnt,d[x]=min(d[x],d[y]+1); //两个链长和超过len，长链断边，取短链长度
  }
}
bool check(){
  cnt=0; //断边次数
  fill(d,d+n+1,0); //清空
  dfs(1,0);
  return cnt<=s; //断边次数少，则len仍大，游标左移
}
int main(){
  scanf("%d%d",&n,&s);
  for(int i=1,u,v;i<n;++i){
    scanf("%d%d",&u,&v);
    add(u,v),add(v,u);
  }
  int l=-1,r=n/s+1;
  while(l+1<r){
    len=l+r>>1;
    if(check()) r=len;
    else l=len;
  }
  printf("%d\n",r);
}