BZOJ2097: [Usaco2010 Dec]Exercise 奶牛健美操 二分答案+贪心+DP

题解:

首先答案显然具有单调性，我们考虑二分答案。

考虑如果需要让最大的直径$\leq{limit}$，最少需要删掉的边数是多少。

我们考虑贪心，从底向上进行考虑，对于一个点作为父亲的情况，考虑所有儿子，将它们按照最长延伸从小到大排序，我们贪心的删掉最长延伸最大的儿子的父亲边直到目前的直径$\leq{limit}$。

不过这样为什么是对的呢？

有可能在儿子子树里面多删一些边使得儿子的最长延伸减少，不过就算只多删一条边，也只能减小这个儿子在父亲上的排名，在父亲上多删一条边一定比在子树里删边划算。

这样大概就可以证明是对的了吧。

时间复杂度$O(nlog^2n)$。

代码：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
	static int q=1;
	end[q]=b;
	next[q]=head[a];
	head[a]=q++;
}
inline void make(int a,int b){
	addedge(a,b);
	addedge(b,a);
}

int f[N];

inline int dfs(int x,int fa,int lim){
	int ans=0;
	vector<int>sav;
	for(int j=head[x];j;j=next[j]){
		if(end[j]!=fa){
			ans+=dfs(end[j],x,lim);
			sav.push_back(f[end[j]]+1);
		}
	}
	sav.push_back(0);
	sav.push_back(0);
	sort(sav.begin(),sav.end());
	int i=sav.size()-1;
	while(((f[x]=sav[i])+sav[i-1])>lim)
		--i;
	return ans+sav.size()-1-i;
}

int main(){
	int n,k;
	cin>>n>>k;
	int i,j,a,b;
	for(i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		make(a,b);
	}
	
	int L=0,R=n-1,mid;
	while(L<R){
		mid=(L+R)>>1;
		if(dfs(1,-1,mid)<=k)
			R=mid;
		else
			L=mid+1;
	}
	cout<<L<<endl;
	
	return 0;
}