BZOJ 2097 Exercise 奶牛健美操 二分答案+樹形DP+貪心
題目大意：給定一棵樹，可以刪掉k條邊，求刪掉後森林中所有樹直徑的最大值的最小值
最大值最小，典型的二分答案
此題我們二分樹的直徑，每次二分DFS一次，對於每個節點統計出所有子樹刪邊後的dis，排序，貪心刪掉最大的，直到最大的兩個子樹相加不會超過二分的答案為止
時間復雜度O(nlog^2n)
老子的二分居然寫掛了。。。桑不起啊啊啊啊
#include
#include
#include
#include
#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>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
