题目链接
树剖傻逼题，练练手好久没写树剖了。
查询忘记(pushdown)抓了好久虫。。
全文手写，一遍过。。。
#include <cstdio>
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
", Query(1, 1, n, pos[b]));
}
return 0;
}