subject

Title Link: https://codeforces.com/contest/1626/problem/E
A tree with \ (n \) nodes. The nodes have black and white colors, and the number of black spots is at least \ (2 \).
At the beginning, there is a stone at a certain point in the tree. You can select a black point for each operation and let the stone go one side in the direction of the black point. You cannot select the same black spot for two consecutive operations.
For each point, find out if there is a way to move the stone to the black point if the stone is at this point.
\(n\leq 3\times 10^5\).

thinking

Set the point \ (1 \) as the root, and consider how the stone can be moved to the black point when the point \ (1 \).

• If there are black spots around point \ (1 \), or point \ (1 \) is a black spot, it is obviously solvable.
• If there are two black spots that form a relationship between grandparents and grandchildren, you only need to constantly select these two black spots.
• If there is no ancestral relationship between two black spots, if the stone wants to reach the black spot \ (x \), the last step can only choose \ (x \) to move, it must reach the father of \ (x \) through other black spots, that is, there must be other black spots in the subtree of the father of \ (x \).
  If there are other black spots \ (y \) in the subtree of the father of \ (x \), you can move to \ (x \), just keep selecting \ (x \) and \ (y \), and select \ (x \) again after reaching the father of \ (x \).

The latter two points are equivalent to taking out the father of each black spot, and then there are two fathers who are grandparents and grandchildren.
That is, after marking the subtree of each black dot father with \ (+ 1 \), there is a node marked with at least \ (2 \).
Directly maintain the global maximum value of the segment tree, and then maintain it when changing the root.
Time complexity \ (O(n\log n) \).

code

#include <bits/stdc++.h>
using namespace std;

const int N=300010;
int n,tot,head[N],a[N],b[N],id[N],siz[N],L[N],R[N];
bool ans[N];

struct edge
{
	int next,to;
}e[N*2];

void add(int from,int to)
{
	e[++tot]=(edge){head[from],to};
	head[from]=tot;
}

struct SegTree
{
	int mx[N*4],lazy[N*4];
	
	void pushdown(int x)
	{
		if (!lazy[x]) return;
		mx[x*2]+=lazy[x]; lazy[x*2]+=lazy[x];
		mx[x*2+1]+=lazy[x]; lazy[x*2+1]+=lazy[x];
		lazy[x]=0;
	}
	
	void update(int x,int l,int r,int ql,int qr,int v)
	{
		if (ql>qr) return;
		if (ql<=l && qr>=r) { mx[x]+=v; lazy[x]+=v; return; }
		pushdown(x);
		int mid=(l+r)>>1;
		if (ql<=mid) update(x*2,l,mid,ql,qr,v);
		if (qr>mid) update(x*2+1,mid+1,r,ql,qr,v);
		mx[x]=max(mx[x*2],mx[x*2+1]);
	}
}seg;

void dfs1(int x,int fa)
{
	id[x]=++tot; siz[x]=1;
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		b[x]+=a[v];
		if (v!=fa) dfs1(v,x),siz[x]+=siz[v];
	}
	L[x]=id[x]; R[x]=id[x]+siz[x]-1;
	if (x!=1) seg.update(1,1,n,L[x],R[x],b[x]-a[fa]);
}

void dfs2(int x,int fa)
{
	ans[x]=a[x]|b[x]|(seg.mx[1]>=2);
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		if (v!=fa)
		{
			seg.update(1,1,n,L[v],R[v],-(b[v]-a[x]));
			seg.update(1,1,n,1,L[v]-1,b[x]-a[v]);
			seg.update(1,1,n,R[v]+1,n,b[x]-a[v]);
			dfs2(v,x);
			seg.update(1,1,n,L[v],R[v],b[v]-a[x]);
			seg.update(1,1,n,1,L[v]-1,-(b[x]-a[v]));
			seg.update(1,1,n,R[v]+1,n,-(b[x]-a[v]));
		}
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	tot=0;
	dfs1(1,0); dfs2(1,0);
	for (int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}