题意：有三个操作
操作 1：表示节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。
操作 2：表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。
询问 3：华华需要给出 i 节点此时的权值。
解法：
把整棵树进行离线操作
先对这棵树进行dfs，一棵子树上的节点是连续的，加权值的时候直接把整颗子树加上权值即可，后面可以把新加上的点的权值清空。
当进行操作1的时候，把这个点的权值清零
当进行操作2的时候，把这个节点i的子树的所有结点权值加上a
当进行操作3的时候，查询这个结点i的权值
dfn[i]记录点i在树状数组上的位置，sz[i]是节点i的子树的大小
#include <bits/stdc++.h>
using namespace std;
const int M = 4e5 + ;
int cnt, tot, n;
struct Edge{
int next, to;
}edge[M * ];
struct node{
int opt, pos, x;
}a[M];
int dfn[M], sz[M], head[M], bit[M];
void add_egde(int u, int v) {
//printf("u %d v %d\n", u, v);
edge[++tot].next = head[u];
edge[tot].to = v;
head[u] = tot;
}
int dfs(int u, int fa) {
dfn[u] = ++cnt;
sz[u] = ;
for(int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
void update(int i, int x) {
while(i <= n + ) {
bit[i] += x;
i += i & (-i);
}
}
void add(int l, int r, int val) {
update(l, val);
update(r + , -val);
}
int query(int i) {
int ans = ;
while(i) {
ans += bit[i];
i -= i & (-i);
}
return ans;
}
int main(){
int m;
scanf("%d", &m);
for(int i = ; i <= m; i++) {
scanf("%d%d", &a[i].opt, &a[i].pos);
if(a[i].opt == ) add_egde(a[i].pos, ++n), a[i].pos = n;
if(a[i].opt == ) scanf("%d", &a[i].x);
}
dfs(, -);
for(int i = ; i <= m; i++) {
if(a[i].opt == ) {
int u = a[i].pos;
int val = query(dfn[u]);
add(dfn[u], dfn[u], -val);
}
else if(a[i].opt == ) {
int u = a[i].pos;
int val = a[i].x;
add(dfn[u], dfn[u] + sz[u] - , val);
}
else printf("%d\n", query(dfn[a[i].pos]));
}
return ;
}