[CF343D]Water Tree 树链剖分

[CF343D]

• 模板题，没啥好说的
• 注意线段树空间

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=2<<19;
struct node{int y,n;}e[N<<1];
int lin[N<<1],deep[N],size[N],top[N],setv[N<<1],son[N],fa[N],id[N],tot,len,op,n,m,x,y;
inline int R(){
    int num=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))num=num*10+ch-'0',ch=getchar();
    return num;
}
inline void read(int x,int y)
{e[++len].y=y,e[len].n=lin[x],lin[x]=len;}

void dfs1(int x,int f){
    size[x]=1;
    for(int i=lin[x];i;i=e[i].n){
        int y=e[i].y;
        if(y==f)continue;
        fa[y]=x,deep[y]=deep[x]+1;
        dfs1(y,x);
        size[x]+=size[y];
        son[x]=size[son[x]]<size[y]? y:son[x];
    }
}
void dfs2(int x,int t){
    top[x]=t;id[x]=++tot;
    if(son[x]==0)return;
    dfs2(son[x],t);
    for(int i=lin[x];i;i=e[i].n){
        int y=e[i].y;
        if(y==son[x]||y==fa[x])continue;
        dfs2(y,y);
    }
}

void pushdown(int o){
    int lc=o<<1,rc=o<<1|1;
    if(~setv[o]){
        setv[lc]=setv[rc]=setv[o];
        setv[o]=-1;
    }
}
void update(int o,int L,int R,int ql,int qr,int v){
    int lc=o<<1,rc=o<<1|1,M=L+R>>1;
    if(ql<=L&&R<=qr){
        setv[o]=v;return;
    }
    pushdown(o);
    if(ql<=M)update(lc,L,M,ql,qr,v);
    if(M<qr)update(rc,M+1,R,ql,qr,v);
}
int query(int o,int L,int R,int p){
    int lc=o<<1,rc=o<<1|1,M=L+R>>1;
    if(L==R)return max(0,setv[o]);
    pushdown(o);
    if(p<=M)return query(lc,L,M,p);
    else return query(rc,M+1,R,p);
}
/
void update_son(int x)
{update(1,1,n,id[x],id[x]+size[x]-1,1);}
int queryans(int x)
{return query(1,1,n,id[x]);}
void update_road(int x){
    while(1){
        update(1,1,n,id[top[x]],id[x],0);
        if(id[top[x]]==1)return;
        x=fa[top[x]];
    }
}
/
int main()
{
    //freopen("a.in","r",stdin);
    memset(setv,-1,sizeof(setv));
    n=R();
    rep(i,2,n){
        x=R(),y=R();
        read(x,y),read(y,x);
    }
    dfs1(1,0); dfs2(1,1);
    m=R();
    while(m--){
        op=R(),x=R();
        if(op==1)update_son(x);
        if(op==2)update_road(x);
        if(op==3)queryans(x)==1? puts("1"):puts("0");
    }return 0;
}