Description

华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。
华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：
操作 1：输入格式1 i，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。
操作 2：输入格式 2 i a表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。
但是月月有时会检查华华有没有认真维护这棵树，会作出询问：
询问 3：输入格式3 i，华华需要给出 i 节点此时的权值。
华华当然有认真种树了，不过还是希望能写个程序以备不时之需。

Solution

树上区间操作，考虑用dfs序表示成数组形式，那么就是我们熟悉的序列区间操作了。由于该问题的树会出现节点增加的情况，显然我们在序列操作的时候可以先假设该点已存在，最后计算贡献的时候减去该点的值即可。
那么问题就可以离线解决，先存储所有操作，建树后得到dfs序，接下来就是树状数组的区间加和单点求值了。

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e9 + 7; 
const int N = 1e6 + 5;
int t[N], l[N], r[N], op[N], val[N], a[N], b[N], cnt = 1;
vector<int> G[N];
int lowbit(int x) {
  return x & (-x);
}
void update(int x, int add) {
  while(x < N) {
    t[x] += add;
    x += lowbit(x);
  }
}
int query(int x) {
  int res = 0;
  while(x) {
    res += t[x];
    x -= lowbit(x);
  }
  return res;
}
void dfs(int x, int par) {
  l[x] = ++cnt; // 最小编号
  for(int i = 0; i < G[x].size(); i++) {
    int u = G[x][i];
    dfs(u, x);
  }
  r[x] = cnt; // 最大编号
}
int main() {
  int m; cin >> m;
  for(int i = 1; i <= m; i++) {
    cin >> op[i] >> a[i];
    a[i]++;
    if(op[i] == 1) {
      G[a[i]].push_back(++cnt);
      b[i] = cnt;
    } else if(op[i] == 2) {
      cin >> b[i];
    }
  }
  dfs(1, -1);
  for(int i = 1; i <= m; i++) {
    if(op[i] == 1) {
      val[l[b[i]]] += query(l[a[i]]); // 统计多加出来的部分
    } else if(op[i] == 2) {
      update(l[a[i]], b[i]); // 树状数组的区间更新
      update(r[a[i]] + 1, -b[i]); 

    } else cout << -val[l[a[i]]] + query(l[a[i]]) << "\n"; // 当前的值减去多加的
  }
  return 0;
}