《点的权值为 $20684$》

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
int n, m, r, w[N], wt[N];

namespace Edge {
    int head[N], ide;
    struct EDGE {
        int v, next;
    } edge[N];
    void add(int u, int v) {
        edge[++ide] = {v, head[u]};
        head[u] = ide;
    }
}
using namespace Edge;

namespace Segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    struct ST {
        int v, tag;
    } t[N];
    void push_up(int rt) { t[rt].v = t[ls].v + t[rs].v; }
    void push_down(int rt, int len) {
        if (t[rt].tag < 0) return;
        t[ls] = {t[rt].tag * (len - len / 2), t[rt].tag};
        t[rs] = {t[rt].tag * (len / 2), t[rt].tag};
        t[rt].tag = -1;
    }
    void build(int rt, int l, int r) {
        if (l >= r) return;
        t[rt].tag = -1;
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
    }
    void update(int rt, int l, int r, int x, int y, int v) {
        if (l > y or r < x) return;
        if (x <= l and r <= y) {
            t[rt] = {(r - l + 1) * v, v};
            return;
        }
        push_down(rt, r - l + 1);
        int mid = l + r >> 1;
        update(ls, l, mid, x, y, v);
        update(rs, mid + 1, r, x, y, v);
        push_up(rt);
    }
    int query(int rt, int l, int r, int x, int y) {
        if (l > y or r < x) return 0;
        if (x <= l and r <= y) return t[rt].v;
        push_down(rt, r - l + 1);
        int mid = l + r >> 1;
        return query(ls, l, mid, x, y) + query(rs, mid + 1, r, x, y);
    }
}
using namespace Segtree;

namespace HLD {
    int dep[N], fa[N], son[N], siz[N], idx[N], top[N], cnt;
    void dfs1(int u, int father) {
        dep[u] = dep[father] + 1;
        fa[u] = father;
        siz[u] = 1;
        int maxx = -1;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (v == father) continue;
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > maxx) {
                son[u] = v;
                maxx = siz[v];
            }
        }
    }
    void dfs2(int u, int topf) {
        idx[u] = ++cnt;
        wt[cnt] = w[u];
        top[u] = topf;
        if (!son[u]) return;
        dfs2(son[u], topf);
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (v == fa[u] or v == son[u]) continue;
            dfs2(v, v);
        }
    }
    void update_range(int x, int y, int v) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            update(1, 1, n, idx[top[x]], idx[x], v);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        update(1, 1, n, idx[x], idx[y], v);
    }
    int query_range(int x, int y) {
        int ret = 0;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            ret += query(1, 1, n, idx[top[x]], idx[x]);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        ret += ret + query(1, 1, n, idx[x], idx[y]);
        return ret;
    }
    void update_son(int u, int v) { update(1, 1, n, idx[u], idx[u] + siz[u] - 1, v); }
    int query_son(int u) { return query(1, 1, n, idx[u], idx[u] + siz[u] - 1); }
}
using namespace HLD;

signed main() {
    IOS;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    cin >> m;
    while (m--) {
        int opt, u;
        cin >> opt >> u;
        if (opt == 1) update_son(u, 1);
        else if (opt == 2) update_range(1, u, 0);
        else if (opt == 3) cout << query_range(u, u) << "\n";
    }
    return 0;
}