树剖傻逼题，练练手好久没写树剖了。

查询忘记\(pushdown\)抓了好久虫。。

全文手写，一遍过。。。

#include 
    
     const int MAXN = 500010;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;}struct Edge{    int next, to;}e[MAXN << 1];int num, head[MAXN];inline void Add(int from, int to){    e[++num].to = to; e[num].next = head[from]; head[from] = num;    e[++num].to = from; e[num].next = head[to]; head[to] = num;}int n, m;#define lc (now << 1)#define rc (now << 1 | 1)int val[MAXN << 2], lazy[MAXN << 2];inline void pushup(int now){    val[now] = val[lc] && val[rc];}inline void pushdown(int now){    if(lazy[now] == 1){        lazy[lc] = lazy[rc] = 1;        val[lc] = val[rc] = 0;        lazy[now] = 0;    }    if(lazy[now] == 2){        lazy[lc] = lazy[rc] = 2;        val[lc] = val[rc] = 1;        lazy[now] = 0;    }}void Update(int now, int l, int r, int wl, int wr, int p){    if(l > wr || r < wl) return;    if(l >= wl && r <= wr){ val[now] = p; lazy[now] = p + 1; return; }    pushdown(now);    int mid = (l + r) >> 1;    Update(lc, l, mid, wl, wr, p);    Update(rc, mid + 1, r, wl, wr, p);    pushup(now);}int Query(int now, int l, int r, int p){    if(val[now]) return 1;    if(l == r) return val[now];    pushdown(now);    int mid = (l + r) >> 1;    if(p <= mid) return Query(lc, l, mid, p);    return Query(rc, mid + 1, r, p);}int size[MAXN], son[MAXN], dep[MAXN], top[MAXN], pos[MAXN], ID, f[MAXN];void dfs1(int u, int fa){    dep[u] = dep[f[u] = fa] + 1;    size[u] = 1;    for(int i = head[u]; i; i = e[i].next)       if(e[i].to != fa){         dfs1(e[i].to, u);         size[u] += size[e[i].to];         if(size[e[i].to] > size[son[u]])           son[u] = e[i].to;       }}void dfs2(int u, int tp){    top[u] = tp; pos[u] = ++ID;    if(son[u]) dfs2(son[u], tp);    for(int i = head[u]; i; i = e[i].next)       if(e[i].to != son[u] && e[i].to != f[u])         dfs2(e[i].to, e[i].to);}void root(int u){    while(u){        Update(1, 1, n, pos[top[u]], pos[u], 0);        u = f[top[u]];    }}void child(int u){    Update(1, 1, n, pos[u], pos[u] + size[u] - 1, 1);}int a, b;int main(){    n = read();    for(int i = 1; i < n; ++i) Add(read(), read());    dfs1(1, 0); dfs2(1, 1);    m = read();    while(m--){        a = read(); b = read();        if(a == 1)            child(b);        if(a == 2)            root(b);        if(a == 3)            printf("%d\n", Query(1, 1, n, pos[b]));    }    return 0;}