华华和月月种树 （dfs序建线段树）

题意：
华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。
华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：
操作 1：输入格式1 i，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。
操作 2：输入格式 2 i a表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。
但是月月有时会检查华华有没有认真维护这棵树，会作出询问：
询问 3：输入格式3 i，华华需要给出 i 节点此时的权值。
华华当然有认真种树了，不过还是希望能写个程序以备不时之需。
题解：
dfs序+线段树
这个题的难点就是他会有一个动态增点的过程。
这样的话呢，如果你直接把这个点建立起来不去，那会出现问题的。
比如说根节点1连着2 3两个儿子 但是3儿子是最后建立的，所以你对结点1做2操作时，会把节点三的值也给加上去，这就是本题的难点。
所以为了处理这个问题，你在每次在加入一个新结点时，把当前结点的值给更新为0才对，这里你可以先把那个结点的值给查出来是多少，然后再用更新函数把那个结点的值减去查出来的值即可，（这样做的好处就是可以少写一个update函数），坏处是稍微浪费一点时间。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <cctype>
//#define int long long
#define endl '\n'
using namespace std;
const int maxn = 2e6+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
using namespace std;
vector<int>edge[400010];
int sum[maxn],lazy[maxn];
int a[maxn],b[maxn],cnt;
int in[maxn],out[maxn];
int tot,op[maxn];

void dfs(int u){
    in[u]=++tot;
    for(auto i:edge[u]){
        dfs(i);
    }
    out[u]=tot;
}
void pushdown(int l,int r,int rt){
    if(lazy[rt]){
        int m=(l+r)>>1;
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+= lazy[rt];
        sum[rt<<1]+=lazy[rt]*(m-l+1);
        sum[rt<<1|1]+=lazy[rt]*(r-m);
        lazy[rt]=0;
    }
}

void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&R>=r){
        sum[rt]+=(r-l+1)*c;
        lazy[rt]+=c;
        return ;
    }
    pushdown(l,r,rt);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,l,m,rt<<1);
    if(R>m) update(L,R,c,m+1,r,rt<<1|1);
}

int query(int p,int l,int r,int rt){
    if(l==r){
        return sum[rt];
    }
    pushdown(l,r,rt);
    int m=(l+r)>>1;
    if(p<=m) return query(p,l,m,rt<<1);
    else return query(p,m+1,r,rt<<1|1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    int cnt=1;
    for(int i=1;i<=n;i++){
        cin>>op[i]>>a[i];
        a[i]++;
        if(op[i]==1){
            cnt++;b[i]= cnt;
            edge[a[i]].push_back(cnt);
        }
        else if(op[i]==2) cin>>b[i];
    }
    dfs(1);
    for(int i=1;i<=n;i ++){
        if(op[i]==2){
            update(in[a[i]],out[a[i]],b[i],1,tot,1);
        }
        else if(op[i]==1){
            int t=query(in[b[i]],1,tot,1);
            update(in[b[i]],in[b[i]],-t,1,tot,1);
        }
        else{
            cout<<query(in[a[i]],1,tot,1)<<endl;
        }
    }
    return 0;
}