华华和月月种树

思路

树上对整颗子树进行操作，容易想到用 $dfs$ 序，但是这是一颗动态变化的树，所以我们可以考虑离线操作。

既然是离线操作，那就简单了，先存下一整棵树以及所有的操作，然后按照要求模拟即可：

对于操作二我们直接以最终一整颗树中形态来进行差分 $update$ 。
对于操作一这里就有有一个关键点了，这个时候刚好有一个点加入树里面，因此我们需要记录这个节点初始的 $value$ ，方便后面输出单个节点的权值。
操作三，我们就可以直接输出 $query(l[rt]) - value[rt]$ 这个时候第一步记录的值在这里就排上用场了。

代码

/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define endl '\n'
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')    f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

const int N = 1e5 + 10;

struct Node {
    int op, a, b;
    Node(int _op = 0, int _a = 0, int _b = 0) : op(_op), a(_a), b(_b) {}
};

vector<Node> a;

vector<int> G[N];

int r[N], l[N], tot;

int tree[N], n, m, value[N];

void dfs(int rt, int fa) {
    l[rt] = ++tot;
    for(int i : G[rt]) {
        if(i == fa) continue;
        dfs(i, rt);
    }
    r[rt] = tot;
}

int lowbit(int x) {
    return x & (-x);
}

void update(int rt, int x) {
    while(rt <= tot) {
        tree[rt] += x;
        rt += lowbit(rt);
    }
}

int query(int rt) {
    int ans = 0;
    while(rt) {
        ans += tree[rt];
        rt -= lowbit(rt);
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    m = read(), n = 0;
    for(int i = 1; i <= m; i++) {
        int op = read();
        if(op == 1) {
            int x = read();
            G[x].pb(++n);
            G[n].pb(x);
            a.pb(Node(op, x, n));
        }
        else if(op == 2) {
            int x = read(), y = read();
            a.pb(Node(op, x, y));
        }
        else {
            int x = read();
            a.pb(Node(op, x));
        }
    }
    dfs(0, -1);
    for(auto i : a) {
        int op = i.op;
        if(op == 1) {
            value[i.b] = query(l[i.b]);
        }
        else if(op == 2) {
            update(r[i.a] + 1, -i.b);
            update(l[i.a], i.b);
        }
        else {
            printf("%d\n", query(l[i.a]) - value[i.a]);
        }
    }
    return 0;
}