鄙人不是特别会换根dp，如有不妥，望指正

第九个测试点错误 ！！

大致思想：分别求出当前节点子树及另一部分的最大可移动点的子树大小，如果大于 超标子树的大小 $-n/2$，则为 1

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[1000001],up[1000001],n,fa[1000001],wson2[1000001];
int size[1000001],cnt,head[1000001],wson[1000001],mas[1000001],mis[1000001],ms1[1000001],ms2[1000001],up1[1000001];
struct node{
	int to,next;
}edge[2000001];
void addedge(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u,int fa1)
{
	size[u]=1;
	ms2[u]=10000001;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa1) continue;
		fa[v]=u;
		dfs(v,u);
		size[u]+=size[v];
		if(mas[u]<=size[v])
		{
			mis[u]=mas[u];
			wson[u]=v;
			mas[u]=size[v];
		}
		else if(mis[u]<=size[v])
			mis[u]=size[v];
		if(size[v]<=n/2 && size[v]>=ms1[u])
		{
			ms2[u]=ms1[u];
			ms1[u]=size[v];
		}
		else if(size[v]<=n/2 && size[v]>=ms2[u]) ms2[u]=size[v];
		if(ms1[u]<=n/2 && ms1[u]>=ms1[fa[u]])  // ms1[u] 本子树最大可移动的点,ms2[u]  本子树次大可移动的点 
		{
			if(ms1[fa[u]]<=ms1[u])
			{
				ms2[fa[u]]=ms1[fa[u]];
				wson2[fa[u]]=u;
				ms1[fa[u]]=ms1[u];
			}
		}
		else if(ms1[u]<=n/2 && ms1[u]>=ms2[fa[u]]) ms2[fa[u]]=ms1[u];
	}
}
void dfs2(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		if(v==wson[u])
		{
			up[v]=max(up[u]+size[u]-size[v],mis[u]+1); // up[u] 另一部分最大子树 
		}
		else 
		{
			up[v]=max(up[u]+size[u]-size[v],mas[u]+1);
		}
		dfs2(v,u);
	}
}
void dfs3(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		if(v==wson2[u])
		{
			if(up[v]>ms2[u] && up[v]<=n/2) up1[v]=up[v]; // up1[u] 另一部分最大可移动的点 
			else up1[v]=max(ms2[u],up1[u]);
		}
		else 
		{
			if(up[v]>ms1[u] && up[v]<=n/2) up1[v]=up[v];
			else up1[v]=max(ms1[u],up1[u]);
		}
		dfs3(v,u);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u);
	}
	dfs(1,0);
	dfs2(1,0);
	dfs3(1,0);
	for(int u=1;u<=n;u++)
	{
		if(mas[u]>n/2)
		{
			int k=mas[u]-n/2;
			if(ms1[u]>=k)  f[u]=1;
		}
		else if(up[u]>n/2)
		{
			int k=up[u]-n/2;
			if(up1[u]>=k) f[u]=1;
		}
		else if(mas[u]<=n/2 && up[u]<=n/2) f[u]=1;
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",f[i]);
	}
	return 0;
}