求助,WA on #9
查看原帖
求助,WA on #9
1351126
General0826楼主2024/7/25 11:55
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int man1[N],man2[N],maxs[N],siz[N],n,m,x,y,z,ans[N],up[N];
vector<int>c[N];
void ge(int  v,int w)
{
	if(man1[v]<=w)
	{
		man2[v]=man1[v];
		man1[v]=w;
	}
	else if(man2[v]<w)
		man2[v]=w;
}
void dfs(int cur,int lst)
{
	siz[cur]=1;
	for(auto i:c[cur])
	{
		if(i!=lst)
		{
			dfs(i,cur);
			siz[cur]+=siz[i];
			ge(cur,man1[i]);
			ge(cur,man2[i]);
			if(siz[i]*2<=n) ge(cur,siz[i]);
			if(siz[maxs[cur]]<siz[i])
				maxs[cur]=i;
		}
	}
}
void chk(int cur,int lst)
{
	for(auto i:c[cur])
	{
		if(i!=lst)
		{
			up[i]=up[cur];
			if((n-siz[cur])*2<=n) up[i]=max(up[i],n-siz[cur]);
			if(man1[cur]==man1[i]||man1[cur]==siz[i])
				up[i]=max(up[i],man2[cur]);
			else
				up[i]=max(up[i],man1[cur]); 
			chk(i,cur);
		}
	}
	if(siz[maxs[cur]]*2>n)
	{
		if((siz[maxs[cur]]-man1[maxs[cur]])*2<=n) ans[cur]=1;
		else ans[cur]=0; 
	}
	else if((n-siz[cur])*2>n)
	{
		if((n-siz[cur]-up[cur])*2<=n) ans[cur]=1;
		else ans[cur]=0;
	}
	else
		ans[cur]=1;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		c[x].push_back(y);	
		c[y].push_back(x);
	}	
	dfs(1,0);
	chk(1,0);
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<' ';//printf("%d %d %d %d\n",man1[i],man2[i],siz[i],up[i]);
	}
	//	
	return 0;
}
2024/7/25 11:55
加载中...