华华和月月种树

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>vec[maxn];
int sumn[maxn],m;
int top=1,idmin[maxn],idmax[maxn],b[maxn<<2][4],num,shu[maxn];
int lowbit(int x){
    return x&(-x);
}
void jia(int x,int k){
    for(;x<=num;x+=lowbit(x) )    sumn[x]+=k;
}
int ask(int x){
    int ans=0;
    for(;x;x-=lowbit(x))    ans+=sumn[x];
    return ans;
}
void dfs(int u)
{
    idmin[u]=idmax[u]=++num;
    for(int i=0;i<vec[u].size();i++ )
    {
        int v=vec[u][i];
        dfs(v);
        idmax[u]=max(idmax[u],idmax[v] );
    }
}
int main()
{
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        for(int j=0,lim=2;j<=lim;j++)
        {
            scanf("%d",&b[i][j]);
            if( b[i][0]!=2 )    lim=1;
        }
        b[i][1]++;
        if( b[i][0]==1 )
            vec[ b[i][1] ].push_back(++top) ;
    }
    dfs(1);
    for(int i=1;i<=m;i++)
    {
        int q=b[i][1],w=b[i][2];
        if( b[i][0]==1 )
        {
            int v=vec[q][shu[q]++ ];//是q的第shu[q]个儿子 
            int zhi=ask( idmin[v] );
            jia( idmin[v],-zhi );
            jia( idmin[v]+1,zhi );
        }
        else if( b[i][0]==2 )
        {
            jia( idmin[q],w );
            jia( idmax[q]+1,-w);
        }
        else
            printf("%d\n",ask( idmin[q] ) );
    }
}