这明显是弱智题
树剖套珂朵莉树多简单啊
前置芝士：珂朵莉树
没什么好说的自己看看吧
先树剖一下
第一种操作，把一个点的子树全部变成1
因为做了树剖，所以珂朵莉树区间赋值就可以了
第二种操作就重链往上跳，重链全变成0，珂朵莉树也能完成
第三种操作直接split一下就行
这道题真的很简单，细节看代码（珂朵莉树实际就是一种暴力）
因为数据随机，所以有可能会有点慢
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define N 500005
using namespace std;
inline int read()
{
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
struct edge{
int to,next;
}e[N<<1];
int head[N],cnt=0;
inline void add(register int u,register int v)
{
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}
int n,m;
int size[N],l[N],son[N],dep[N],fa[N],top[N],tot=0;
inline void dfs1(register int x)
{
size[x]=1;
for(register int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!dep[v])
{
dep[v]=dep[x]+1;
fa[v]=x;
dfs1(v);
size[x]+=size[v];
if(size[v]>size[son[x]])
son[x]=v;
}
}
}
inline void dfs2(register int x,register int t)
{
l[x]=++tot;
top[x]=t;
if(son[x])
dfs2(son[x],t);
for(register int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa[x]&&v!=son[x])
dfs2(v,v);
}
}
struct node
{
int l,r;
mutable int v;
node(int L, int R=-1, int V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const
{
return l < o.l;
}
};
set<node> s;
#define IT set<node>::iterator
IT split(register int pos)
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos)
return it;
--it;
int L = it->l, R = it->r;
int V = it->v;
s.erase(it);
s.insert(node(L, pos-1, V));
return s.insert(node(pos, R, V)).first;
}
inline void assign_val(register int l,register int r,register int val)
{
IT itr = split(r+1),itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
inline void query(register int pos)
{
IT itpos = split(pos);
printf("%d\n",itpos->v);
}
inline void cal(register int pos)
{
int fpos=top[pos];
while(fpos!=1)
{
assign_val(l[fpos],l[pos],0);
pos=fa[fpos],fpos=top[pos];
}
assign_val(l[1],l[pos],0);
}
int main()
{
n=read();
for(register int i=1;i<n;++i)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
dep[1]=fa[1]=1;
dfs1(1);
dfs2(1,1);
s.insert(node(0,500000+233));
int m=read();
while(m--)
{
int opt=read(),pos=read();
if(opt==1)
assign_val(l[pos],l[pos]+size[pos]-1,1);
else if(opt==2)
cal(pos);
else
query(l[pos]);
}
return 0;
}