有无人能hack我,有三个点一直过不去
查看原帖
有无人能hack我,有三个点一直过不去
331947
hegm楼主2023/3/14 16:11
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct fig
{
	int to,next;
}k[N*2];int tot,head[N];
int n,lim,in[N];
bool fail;
void add(int from,int to)
{
	k[++tot].to=to;
	k[tot].next=head[from];
	head[from]=tot;
}
int dp[N],id[N];
void dfs(int now,int fa)
{
	if(fail)return;
	int a=0,b=0,c=0,d=0,e=0,x=0,y=0,z=0;
	for(int i=head[now];i;i=k[i].next)
	{
		if(k[i].to==fa)continue;
		dfs(k[i].to,now);
	}
	for(int i=head[now];i;i=k[i].next)
	{
		if(k[i].to==fa)continue;
		if(id[k[i].to]==0&&a<dp[k[i].to])a=dp[k[i].to],x=k[i].to;
		if(id[k[i].to]==1&&d<dp[k[i].to])d=dp[k[i].to],z=k[i].to;
	}
	for(int i=head[now];i;i=k[i].next)if(id[k[i].to]==0&&b<dp[k[i].to]&&k[i].to!=x&&k[i].to!=fa)b=dp[k[i].to],y=k[i].to;
	for(int i=head[now];i;i=k[i].next)if(id[k[i].to]==0&&c<dp[k[i].to]&&k[i].to!=x&&k[i].to!=y&&k[i].to!=fa)c=dp[k[i].to];
	for(int i=head[now];i;i=k[i].next)if(id[k[i].to]==1&&e<dp[k[i].to]&&k[i].to!=z&&k[i].to!=fa)e=dp[k[i].to];
	if(max({a+b-1,a+c,d+a,d+e+1,c+d+1})>lim)
	{
		fail=1;
		return;
	}
	if(max({a+b,b+c+1,a+d,b+1+d})<=lim&&max({a,b+1,d+1})==max({a,b,c+1,d+1}))
	{
		dp[now]=max({a,b+1,d+1});
		id[now]=0;
	}
	else
	{
		dp[now]=max({a,b,c+1,d+1});
		id[now]=1;
	}
}
int main()
{
	n=read();
	for(int i=1,u,v;i<n;i++)
	{
		u=read();v=read();
		add(u,v);add(v,u);
	}
	int l=1,r=n;
	while(l<=r)
	{
		lim=(l+r)>>1;
		fail=0;
		dfs(1,0);
		if(fail)l=lim+1;
		else r=lim-1;
	}
	cout<<r+1<<"\n";
	return 0;
}
2023/3/14 16:11
加载中...