记录编号	550138	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO20 Feb Platinum]Delegation(Platinum)	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	1.986 s
提交时间	2020-03-03 10:51:18	内存使用	19.38 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> b[100001],V[100001];
int up[100001],jl[100001],KES[100001];
int n,m,k,cnt=0,Flag=0,sd=0,a1,a2;
bool Function(int x,int y)
{
	return x<y;
}
bool Check(int x,int p)
{
	int siz=V[x].size();
    for (int i=0,j=siz-1;i<j;i++,j--)
	{
        if(i==p)
		{
			i++;
		}
        if(j==p)
		{
		j--;
		}
        if (V[x][i]+V[x][j]<k)
		{
		return 0;
		}
    }
    return 1;
}
void DFS(int x,int fa)
{
	V[x].clear();
	for(int i=0;i<b[x].size();i++)
	{
		int to=b[x][i];
		if(to==fa)
			continue;
		DFS(to,x);
			V[x].push_back(up[to]+1);
	}
	if(!fa&&(V[x].size()%2==1))
		V[x].push_back(0);
	if(fa&&(V[x].size()%2==0))
		V[x].push_back(0);
	sort(V[x].begin(),V[x].end());
	if(!fa)
	{
		for(int i=0;i<V[x].size()/2;i++)
		{
			if(V[x][i]+V[x][(V[x].size()-i-1)]<k)
			{
				Flag=1;
				return;
			}
		}
		return ;
	}
	if(Check(x,0)==0)
	{
		Flag=1;
		return;
	}
	int L=0,R=V[x].size()-1;
	while(L<R)
	{
		int mid=(L+R+1)>>1;
		if(Check(x,mid))
		{
			L=mid;
		}
		else
			R=mid-1;
	}
	up[x]=V[x][L];
}
void Work()
{
	int L=1,R=n-1,ans=999;
	while(L<R)
	{
		Flag=0;
		int mid=(L+R+1)>>1;
		k=mid;
		DFS(1,0);
		if(Flag==1)
		{
			R=mid-1;
		}
		else
		{
			L=mid;
			ans=mid;
		}
	}
	printf("%d",ans);
	return ;
}
int main()
{
	freopen("usaco_Feb_delegs.in","r",stdin);
	freopen("usaco_Feb_delegs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&a1,&a2);
		b[a1].push_back(a2);
		b[a2].push_back(a1);
	}
	Work();
	return 0;
}