华华和月月种树

题意：
一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：
操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。
操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。
操作3：输入格式为3 i 表示输出i节点的权值。

思路：
建立dfs离散序，化树为序列。（既先序序列）
树状数组维护序列数据。
操作1：将加的节点重置为0；
操作2：将i节点所在的序列位置到i节点所在的序列位置+i节点为根的子树大小-1进行区间加a，以为先序序列子树的是连续的一段，开始位置为根的位置。
操作3：输出结果。

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=1000000007;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int cnt=2, se[100005], vs[100005], ji=1;
ll bit0[100005], bit1[100005];
struct w
{
    int k, i, a;
} w[500005];

vector<int> g[100005];

void add(ll *b,int i,int v)
{
    while(i<=cnt)
    {
        b[i]+=v;
        i+=i&(-i);
    }
}

ll sum(ll *b,int i)
{
    ll s=0;
    while(i>0)
    {
        s+=b[i];
        i-=i&(-i);
    }
    return s;
}

void dfs(int v)
{
    vs[v]=ji++;
    se[v]=1;
    for(int i=0; i<g[v].size(); i++)
    {
        dfs(g[v][i]);
        se[v]+=se[g[v][i]];
    }
}

int main()
{
    int m;
    scanf("%d",&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d",&w[i].k);
        if(w[i].k==1)
        {
            scanf("%d",&w[i].i);
            w[i].i++;
            g[w[i].i].push_back(cnt);
            w[i].i=cnt;
            cnt++;
        }
        else if(w[i].k==2)
        {
            scanf("%d %d",&w[i].i,&w[i].a);
            w[i].i++;
        }
        else
        {
            scanf("%d",&w[i].i);
            w[i].i++;
        }
    }
    memset(bit1,0,sizeof(bit1));
    memset(bit0,0,sizeof(bit0));
    dfs(1);
    for(int i=0; i<m; i++)
    {
        int q=w[i].k;
        if(q==1)
        {
            int v=w[i].i;
            ll pa=sum(bit0,vs[v])+sum(bit1,vs[v])*vs[v];
            pa=pa-sum(bit0,vs[v]-1)-sum(bit1,vs[v]-1)*(vs[v]-1);
            add(bit0,vs[v],-pa);
        }
        else if(q==2)
        {
            int l=vs[w[i].i], r=l+se[w[i].i]-1;
            add(bit0,l,-w[i].a*(l-1));
            add(bit1,l,w[i].a);
            add(bit0,r+1,w[i].a*r);
            add(bit1,r+1,-w[i].a);
        }
        else
        {
            int v=w[i].i;
            ll pa=sum(bit0,vs[v])+sum(bit1,vs[v])*vs[v];
            pa=pa-sum(bit0,vs[v]-1)-sum(bit1,vs[v]-1)*(vs[v]-1);
            printf("%lld\n",pa);
        }
    }
    return 0;
}