然而并不会珂朵莉树，也不会珂朵莉树上树

这树剖裸题啊!感觉难度应该是提高+/省选-

我们将这棵树剖完之后,再看三个操作：

操作1：区间覆盖1

操作2：区间覆盖0

操作3：单点查询

用线段树维护区间1的数量

如果中途访问到的区间1的数量等于区间长度，直接返回1，否则访问线段树叶子结点，注意laz数组初始值为-1,0为0覆盖整个区间，1为1覆盖整个区间。

这样down的时候可以直接用区间长度乘laz，down完之后laz回归初始值-1。

然后就完了。

#include<iostream>
#include<cstdio>
#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=500005;
int n,m,cnt,tot;
int head[N],dep[N],fa[N],siz[N],son[N],id[N],top[N];
int tr[N<<2],laz[N<<2];
struct node{
    int to,nxt;
}e[N<<1];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline void add(int from,int to){
    e[++cnt]=(node){to,head[from]};
    head[from]=cnt;
}
void dfs1(int x,int f,int deep){
    fa[x]=f;siz[x]=1;dep[x]=deep;
    int maxson=-1,to;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=f){
            to=e[i].to;
            dfs1(to,x,deep+1);
            siz[x]+=siz[to];
            if(siz[to]>maxson)son[x]=to,maxson=siz[to];
        }
}
void dfs2(int x,int topf){
    id[x]=++tot;top[x]=topf;
    if(!son[x])return ;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
            dfs2(e[i].to,e[i].to);
}
inline void update(int k){
    tr[k]=tr[ls]+tr[rs];
}
inline void down(int k,int l,int r){
    tr[ls]=(mid-l+1)*laz[k];
    tr[rs]=(r-mid)*laz[k];
    laz[ls]=laz[rs]=laz[k];
    laz[k]=-1;
}
void change(int k,int l,int r,int x,int y,int z){
    if(x==l&&y==r){
        tr[k]=(r-l+1)*z;
        laz[k]=z;
        return ;
    }
    if(laz[k]!=-1)down(k,l,r);
    if(y<=mid)change(lson,x,y,z);
    else if(x>mid)change(rson,x,y,z);
    else change(lson,x,mid,z),change(rson,mid+1,y,z);
    update(k);
}
int ask(int k,int l,int r,int x){
    if(tr[k]==(r-l+1))return 1;
    if(l==r&&l==x){
        return tr[k];
    }
    if(laz[k]!=-1)down(k,l,r);
    if(x<=mid)return ask(lson,x);
    else return ask(rson,x);
}
inline void chenge(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        change(1,1,n,id[top[x]],id[x],0);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,1,n,id[x],id[y],0);
}
int main(){
    n=read();
    int x,y;
    for(int i=1;i<n;++i){
        x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for(int i=1;i<=(n<<2);++i)laz[i]=-1;
    m=read();
    int opt;
    while(m--){
        opt=read();x=read();
        if(opt==1)change(1,1,n,id[x],id[x]+siz[x]-1,1);
        else if(opt==2)chenge(x,1);
        else printf("%d\n",ask(1,1,n,id[x]));
    }
    return 0;
}