不知道咋的,的2个点mle
查看原帖
不知道咋的,的2个点mle
230015
SuHo_大水怪楼主2021/6/28 15:56
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int n,cnt=0,heads[N],f[N];
struct ed{
	int next,to;
}	edge[N];
void add(int x,int y)
{
	cnt++;
	edge[cnt].next=heads[x];
	edge[cnt].to  =y;
	heads[x]      =cnt;
}
int DP(int x,int k,int father)
{
	
	int waste=1;
	for(int i=heads[x];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v == father)	continue;
		waste += DP(v,k,x);
	}
	waste = waste - k;
	if(waste > 1)	return waste;
	else return 1;
}
bool dfs(int k)
{
	int h=DP(1,k,0);
	if( h > 1 )	return false;
	else	return true;
}
int check(int l,int r)
{	
	if(l==r)	return l;
	int mid=(l+r)/2;
	if(dfs(mid) == false)	return check(mid+1,r);
	else 			return check(l,mid);
}
int main()
{
	cin>>n;
	int a,b;
	for(int i=1;i<=n-1;i++)
	{
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	cout<<check(1,n-1);
	return 0;
}
2021/6/28 15:56
加载中...