代码贴 $2$ 楼了。
```cpp
#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int N = 1000010, M = 50010;
// 两种 lazy-tag
// 1. 子树修改 mt(u) (modify-tree)
// 2. 路径修改 mp(u) (modify-path)
struct Query {
int op, u;
}; vector<Query> Q;
vector<int> vec[M];
int f[N], g[N], col[N], n, m, B;
int mt[N], mp[N], h[N], e[N], ne[N], idx;
int fa[N], dep[N], top[N], sz[N], son[N];
int get(int x) { return (x / B) + 1; }
void add(int a, int b) {
e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
void dfs1(int u, int F) {
fa[u] = F, dep[u] = dep[F] + 1, sz[u] = 1;
for (int i = h[u]; i; i = ne[i]) {
int v = e[i];
if (v == F) continue;
dfs1(v, u); sz[u] += sz[v];
if (sz[v] > sz[son[u]])
son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int i = h[u]; i; i = ne[i]) {
int v = e[i];
if (v == fa[u] or v == son[u]) continue;
dfs2(v, v);
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return u;
}
void dfs(int u, int F) {
f[u] = max(f[u], mt[u]);
g[u] = max(g[u], mp[u]);
for (int i = h[u]; i; i = ne[i]) {
int v = e[i]; if (v == F) continue;
f[v] = max(f[v], f[u]); dfs(v, u);
g[u] = max(g[u], g[v]);
}
}
void modify(int c) { // 修改第 c 块
for (auto i : vec[c]) {
int op = Q[i].op, u = Q[i].u;
if (op == 1) mt[u] = i;
if (op == 2) mp[u] = i;
} dfs(1, 0);
for (int i = 1; i <= n; i ++ )
if (f[i] > g[i]) col[i] = 1;
else col[i] = 0;
}
void query(int c) {
auto &t = vec[c];
for (int i = 0; i < t.size(); i ++ ) {
int op = Q[t[i]].op, u = Q[t[i]].u;
if (op == 3) printf("%d\n", col[u]);
if (op == 2) {
for (int j = i + 1; j < t.size(); j ++ ) {
int oq = Q[t[j]].op, v = Q[t[j]].u;
if (oq == 3 and lca(u, v) == v) col[v] = 0;
}
}
if (op == 1) {
for (int j = i + 1; j < t.size(); j ++ ) {
int oq = Q[t[j]].op, v = Q[t[j]].u;
if (oq == 3 and lca(u, v) == u) col[v] = 1;
}
}
}
}
int main() {
scanf("%d", &n); Q.push_back({0, 0});
for (int i = 1; i < n; i ++ ) {
int a, b; scanf("%d%d", &a, &b);
add(a, b), add(b, a);
} scanf("%d", &m);
for (int i = 1; i <= m; i ++ ) {
int op, u; scanf("%d%d", &op, &u);
Q.push_back({op, u});
} B = max(1, (int)sqrt((double)m / log2(n)));
for (int i = 1; i <= m; i ++ )
vec[get(i)].push_back(i);
dep[1] = 1; dfs1(1, 0); dfs2(1, 1);
for (int i = get(1); i <= get(m); i ++ )
query(i), modify(i);
return 0;
}
```
by Link_Cut_Y @ 2023-09-22 21:30:05
@[Link_Cut_Y](/user/519384) lca换成倍增试试
by sxy2012yutiti @ 2023-09-22 21:43:21
@[sxy2012yutiti](/user/729386) 哥你别啊，倍增比树剖慢啊。
by Link_Cut_Y @ 2023-09-22 21:44:50
@[Link_Cut_Y](/user/519384) 噢，没学过树剖
by sxy2012yutiti @ 2023-09-22 21:45:46
代码没怎么看懂，但是st表是不是可以o1 lca，（只是看到了lca想起来的可能毫无帮助）
by 天才颓废学家 @ 2023-09-22 22:24:40
确实啊，为啥不用 $O(1)$ LCA
by Lagerent @ 2023-09-23 07:22:53
@[Lagerent](/user/477674) 艹，不会写四毛子。
by RegisterFault @ 2023-09-23 07:28:00