题目链接

• Water Tree
  • 这是一道树链剖分+DFS序题，较为典型且易于思考。
  • 树链剖分的经典模板就是按照DFS序建立线段树，只要在第2次DFS时顺便记录每个结点的入序和出序即可，为操作1提供了方便。
  • 操作1是把一个结点的所有子结点全部注水，这一操作即为DFS序的经典操作，这里不再赘述。
  • 操作2是把一个结点及其所有父结点的水清空，我们可以沿着重链不断攀升，每次修改一整条链，直至到达根结点为止。

代码：

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=(int)5e5+10;
struct Edge
{
	int to,next;
}edge[maxn<<1];
int head[maxn],tot,top[maxn],fa[maxn],deep[maxn],num[maxn],p[maxn],fp[maxn],son[maxn],pos;
void init()
{
	tot=pos=0;
	memset(head,-1,sizeof(head));
	memset(son,-1,sizeof(son));
}
void addedge(int u,int v)
{
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void dfs1(int u,int pre,int d)
{
	deep[u]=d;
	fa[u]=pre;
	num[u]=1;
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=pre)
		{
			dfs1(v,u,d+1);
			num[u]+=num[v];
			if(son[u]==-1||num[v]>num[son[u]])
			{
				son[u]=v;
			}
		}
	}
}
int L[maxn],R[maxn];
void get_pos(int u,int sp)
{
	top[u]=sp;
	p[u]=++pos;
	L[u]=pos;
	fp[p[u]]=u;
	if(son[u]==-1)
	{
		R[u]=pos;
		return;
	}
	get_pos(son[u],sp);
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=son[u]&&v!=fa[u])
		{
			get_pos(v,v);
		}
	}
	R[u]=pos;
}
struct Node
{
	int l,r,sum,lazy;
	bool is_lazy;
}segTree[maxn<<2];
void build(int i,int l,int r)
{
	segTree[i].is_lazy=false;
	segTree[i].l=l;
	segTree[i].r=r;
	segTree[i].sum=segTree[i].lazy=0;
	if(l==r)
	{
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
}
inline void push_up(int i)
{
	segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum;
}
inline void push_down(int i,int ln,int rn)
{
	if(segTree[i].is_lazy)
	{
		segTree[i<<1].is_lazy=segTree[i<<1|1].is_lazy=true;
		segTree[i<<1].lazy=segTree[i<<1|1].lazy=segTree[i].lazy;
		segTree[i<<1].sum=segTree[i].lazy*ln;
		segTree[i<<1|1].sum=segTree[i].lazy*rn;
		segTree[i].is_lazy=false;
	}
}
void update(int i,int l,int r,int val)
{
	if(segTree[i].l>=l&&segTree[i].r<=r)
	{
		segTree[i].sum=val*(segTree[i].r-segTree[i].l+1);
		segTree[i].lazy=val;
		segTree[i].is_lazy=true;
		return;
	}
	int mid=(segTree[i].l+segTree[i].r)>>1;
	push_down(i,mid-segTree[i].l+1,segTree[i].r-mid);
	if(l<=mid)
	{
		update(i<<1,l,r,val);
	}
	if(r>mid)
	{
		update(i<<1|1,l,r,val);
	}
	push_up(i);
}
int query(int i,int l,int r)
{
	if(segTree[i].l>=l&&segTree[i].r<=r)
	{
		return segTree[i].sum;
	}
	int mid=(segTree[i].l+segTree[i].r)>>1;
	push_down(i,mid-segTree[i].l+1,segTree[i].r-mid);
	int ans=0;
	if(l<=mid)
	{
		ans+=query(i<<1,l,r);
	}
	if(r>mid)
	{
		ans+=query(i<<1|1,l,r);
	}
	return ans;
}
inline void dry(int u)
{
	int x=top[u];
	while(x!=1)
	{
		update(1,p[x],p[u],0);
		u=fa[x];
		x=top[u];
	}
	update(1,p[1],p[u],0);
}
int e[maxn][2];
int main()
{
	init();
	int n;
	scanf("%d",&n);
	for(int i=0;i<n-1;++i)
	{
		scanf("%d%d",&e[i][0],&e[i][1]);
		addedge(e[i][0],e[i][1]);
		addedge(e[i][1],e[i][0]);
	}
	dfs1(1,0,0);
	get_pos(1,1);
	build(1,1,pos);
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int op,opr;
		scanf("%d%d",&op,&opr);
		if(op==1)
		{
			update(1,L[opr],R[opr],1);
		}
		else if(op==2)
		{
			dry(opr);
		}
		else
		{
			printf("%d\n",(query(1,L[opr],R[opr])==R[opr]-L[opr]+1)?1:0);
		}
	}
	return 0;
}