Description
给出一棵树，N(2 <= N <= 100,000)个结点。每条边的长度为1。最多删掉树上的S(1 <= S <= N-1)条边,将树分割成S+1块,使得所有块的最长链的最大值最小。
Input
第1行：2个整数，N和S 接下来N-1行，每行2个整数，表示一条边
Output
一个整数，表示最长链的最小值
Sample Input 1
7 2
6 7
3 4
6 5
1 2
3 2
4 5
Sample Output 1
2
Hint
2 <= N <= 100,000
看到问题是最大值最小，二分猜答案没跑了。
问题是猜到答案过后怎么验证。
想到可以记录节点u到叶子的最远和次远距离，它们之和就是u的子树里的最长链
用dp[u]表示u到叶子节点的最远距离，新遍历完一个子树v后，如果dp[v]+dp[u]>猜的答案，就删除一条边，贪心思路选择删除dp[u]和dp[v]里最大的一个子树，保留较小的。如果不需要删除，就找dp[u]=max(dp[u],dp[v])
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define maxn 100005
using namespace std;
int fir[maxn],ne[maxn*2],to[maxn*2],newp=0;
void add(int x,int y){
ne[++newp]=fir[x];
fir[x]=newp;
to[newp]=y;
}
int dis[maxn];
int cnt,mid;
int n,s;
void dfs(int f,int u){
if(cnt>s)return;
dis[u]=0;
for(int i=fir[u];i;i=ne[i]){
int v=to[i];
if(v==f)continue;
dfs(u,v);
if(dis[u]+dis[v]>mid)
cnt++,dis[u]=min(dis[u],dis[v]);
else dis[u]=max(dis[u],dis[v]);
}
dis[u]++; //这里++后变为fa[u]在u这个子树里离叶子的最远距离
}
inline bool check(int mid){
cnt=0;
dfs(0,1);
return cnt<=s;
}
int main(){
scanf("%d%d",&n,&s);
for(int i=1,a,b,c;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
int l=0,r=n,ans;
while(l<=r){
mid=l+r>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}