BZOJ 2097 Exercise 奶牛健美操 二分答案+树形DP+贪心

题目大意：给定一棵树，可以删掉k条边，求删掉后森林中所有树直径的最大值的最小值

最大值最小，典型的二分答案

此题我们二分树的直径，每次二分DFS一次，对于每个节点统计出所有子树删边后的dis，排序，贪心删掉最大的，直到最大的两个子树相加不会超过二分的答案为止

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

老子的二分居然写挂了。。。桑不起啊啊啊啊

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100100
using namespace std;
struct abcd{
	int to,next;
}table[M<<1];
int head[M],tot;
int n,m,ans;
int fa[M],dis[M],stack[M],top;
void Add(int x,int y)
{
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
void Tree_DP(int x,int limit)
{
	int i,bottom=top;
	for(i=head[x];i;i=table[i].next)
	{
		if(table[i].to==fa[x])
			continue;
		fa[table[i].to]=x;
		Tree_DP(table[i].to,limit);
		stack[++top]=dis[table[i].to]+1;
	}
	sort(stack+bottom+1,stack+top+1);
	for(i=top;i>bottom;i--)
		if(stack[i]>limit||i>bottom+1&&stack[i]+stack[i-1]>limit)
			++ans;
		else
			break;
	dis[x]=i==bottom?0:stack[i];
	top=bottom;
}
int Bisection()
{
	int l=1,r=n;
	while(l+1<r)
	{
		int mid=l+r>>1;
		ans=0;Tree_DP(1,mid);
		if(ans>m)
			l=mid;
		else
			r=mid;
	}
	ans=0;Tree_DP(1,l);
	if(ans<=m)
		return l;
	return r;
}
int main()
{
	int i,x,y;
	cin>>n>>m;
	for(i=1;i<n;i++)
		scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
	printf("%d\n", Bisection() );
}

BZOJ 2097 Exercise 奶牛健美操 二分答案+树形DP+贪心

原文：http://blog.csdn.net/popoqqq/article/details/40051799