题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2097
二分答案，然后找以每个点儿子为根的最长链，把它们排序，从大到小扫，如果有相邻两个加在一起大于了二分的ans，那么说明一定要在中间截一下，然后再更新当前点的最长链
注意特判下最小的那个是否大于ans
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<bits/stdc++.h> #define MAXN 100010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m,sz[MAXN],a[MAXN],tot,cnt; vector<int>v[MAXN]; void dfs(int x,int fa,int num){ sz[x]=0; bool f=false; for(int i=0; i<v[x].size(); i++){ int to=v[x][i]; if(to==fa)continue; f=1; dfs(to,x,num); if(sz[to]+1>sz[x])sz[x]=sz[to]+1; } if(!f)return; tot=0; for(int i=0; i<v[x].size(); i++)if(v[x][i]!=fa)a[++tot]=sz[v[x][i]]+1; sort(a+1,a+tot+1); for(int i=tot; i>1; i--)if(a[i]+a[i-1]>num)cnt++,a[i]=0; if(a[1]>num)cnt++,a[1]=0; sort(a+1,a+tot+1); sz[x]=a[tot]; } inline bool check(int num){ cnt=0; dfs(1,0,num); return cnt<=m; } int main(){ n=rd(),m=rd(); for(int i=1; i<n; i++){ int x=rd(),y=rd(); v[x].push_back(y); v[y].push_back(x); } int l=0,r=n-1,ans; while(l<=r){ int mid=(l+r)/2; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0; } |