华华和月月种树

题目地址：

https://ac.nowcoder.com/acm/problem/23051

基本思路：

我们考虑先离线,将树建出来,然后在序上用差分树状数组维护,
但是在这样做的过程中,对于每次的操作二,有些实际还没有被加入的点也被算了权值,
所以我们在每次新加点的时候记录一下,这个点被加进来的时候已经有多少权值了,
很明显这部分权值是无效的,我们在之后的查询里去除这部分就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 4e5 + 10;
int m,op[maxn],pos[maxn],a[maxn],w[maxn];
int L[maxn],R[maxn],tot;
vector<int> G[maxn];
void dfs(int u,int par){
  L[u] = ++tot;
  for(auto to : G[u]){
    if(to == par) continue;
    dfs(to,u);
  }
  R[u] = tot;
}
struct BIT{
    int t[maxn << 2];
    int lowbit(int x){
      return x & (-x);
    }
    void clear(){
      memset(t,0,sizeof(t));
    }
    int sum(int x){
      int res = 0;
      while(x){
        res += t[x];
        x -= lowbit(x);
      }
      return res;
    }
    void update(int x,int v){
      while(x <= tot + 1){
        t[x] += v;
        x += lowbit(x);
      }
    }
}bit;
signed main() {
  m = read();
  int cnt = 0;
  rep(i, 1, m) {
    op[i] = read(), pos[i] = read();
    if (op[i] == 2) a[i] = read();
    else if (op[i] == 1) {
      G[pos[i]].pb(++cnt);
      G[cnt].push_back(pos[i]);
      a[i] = cnt; // 记录一下这次加入的是哪个点;
    }
  }
  dfs(0, -1);
  bit.clear();
  for (int i = 1; i <= m; i++) {
    if (op[i] == 1) {
      w[L[a[i]]] = bit.sum(L[a[i]]); //在这之前被计算的权值是无效的,因为之前还不存在这个点;
    } else if (op[i] == 2) {
      bit.update(L[pos[i]], a[i]); // 在树状数组上差分;
      bit.update(R[pos[i]] + 1, -a[i]);
    } else {
      int ans =  bit.sum(L[pos[i]]) - w[L[pos[i]]]; // 总的权值减去无效的部分;
      print(ans);
      puts("");
    }
  }
  return 0;
}