1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include<bits/stdc++.h>
#define ll long long
#define INF 2147483647
#define lc(a) (a << 1)
#define rc(a) (a << 1 | 1)
int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}
struct SEG_Tree{
struct SEG{
int l;
int r;
int max;
int lazy;
}t[2000000];
void push_up(int cur){
t[cur].max = std::max(t[lc(cur)].max, t[rc(cur)].max);
}
void push_down(int cur){
if(!t[cur].lazy)
return ;
t[lc(cur)].max = t[rc(cur)].max = t[lc(cur)].lazy = t[rc(cur)].lazy = t[cur].lazy;
t[cur].lazy = 0;
}
void build(int cur, int l, int r){
t[cur].l = l;
t[cur].r = r;
t[cur].max = 0;
t[cur].lazy = 0;
if(l == r)
return ;
int mid = (l + r) >> 1;
build(lc(cur), l, mid);
build(rc(cur), mid + 1, r);
}
void modify(int cur, int l, int r, int c){
if(t[cur].l > r || t[cur].r < l)
return ;
if(t[cur].l >= l && t[cur].r <= r){
t[cur].max = c;
t[cur].lazy = c;
return ;
}
push_down(cur);
modify(lc(cur), l, r, c);
modify(rc(cur), l, r, c);
push_up(cur);
}
int query(int cur, int l, int r){
if(t[cur].l > r || t[cur].r < l)
return 0;
if(t[cur].l >= l && t[cur].r <= r)
return t[cur].max;
push_down(cur);
return std::max(query(lc(cur), l, r), query(rc(cur), l, r));
}
}t1, t2;
int dfn[500010], size[500010], head[500010], nxt[1000010], end[1000010];
int cou = 0;
void link(int a, int b){
nxt[++cou] = head[a];
head[a] = cou;
end[cou] = b;
}
int idx = 0;
void dfs(int cur, int last){
dfn[cur] = ++idx;
size[cur] = 1;
for(int x = head[cur]; x != -1; x = nxt[x])
if(end[x] != last){
dfs(end[x], cur);
size[cur] += size[end[x]];
}
}
int main(){
memset(head, -1, sizeof(head));
int n = inp();
for(int i = 1; i < n; i++){
int u = inp();
int v = inp();
link(u, v);
link(v, u);
}
int m = inp();
dfs(1, 0);
t1.build(1, 1, n);
t2.build(1, 1, n);
for(int i = 1; i <= m; i++){
int op = inp();
if(op == 1){
int x = inp();
t1.modify(1, dfn[x], dfn[x] + size[x] - 1, i);
} else if(op == 2){
int x = inp();
t2.modify(1, dfn[x], dfn[x], i);
} else {
int x = inp();
int a1 = t1.query(1, dfn[x], dfn[x]);
int a2 = t2.query(1, dfn[x], dfn[x] + size[x] - 1);
if(a1 > a2)
printf("1\n");
else
printf("0\n");
}
}
}
|
