华华和月月种树-题解

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

输入描述:
第一行一个正整数M，接下来M行，每行先输入一个正整数O表示操作类型，再输入一个非负整数i表示操作或询问的节点编号，如果O=2，再输入一个正整数a。

思路：首先这是一棵树，我们采用离线的做法先将这颗树建好，然后跑一遍dfs序，记录子树大小。针对操作1我们只需要将该点的权值设置为0就行，至于为啥不用修改子孙节点，这是因为子孙节点一定是在当前节点之后才长出的，所以我们只需在下一次操作1修改就行。针对操作2，我们就需要更新该节点以及他的子孙节点了。剩下的操作3就是查询操作了。这里涉及到单点修改，区间修改，单点查询，经典线段树嘛。

代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[400005],lazy[400005],siz[400005],vis[400005];
int sum[400005],id=0;
vector<int>edge[400005];
struct Node{
    int op,pos,w;
}b[400005];
int dfs(int u)//跑出dfs序用来跑线段树
{
    vis[u]=++id;//记录该节点的访问时间即时间戳
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        siz[u]+=dfs(v);
    }
    return siz[u]+1;//子树大小不包括自己，方便在dfs序中更新子孙节点
}
void pushdown(int p)//线段树向下更新
{
    if(lazy[p]){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
        sum[p*2]+=lazy[p];
        sum[p*2+1]+=lazy[p];
        lazy[p]=0;
    }
}
void updateone(int p,int l,int r,int pos)//单点修改
{
    if(l==r){
        sum[p]=0;
        return;
    }
    pushdown(p);
    int mid=(l+r)/2;
    if(pos<=mid)updateone(p*2,l,mid,pos);
    else updateone(p*2+1,mid+1,r,pos);
}
void updatemul(int p,int l,int r,int ul,int ur,int w)//区间修改
{
    if(ul<=l&&ur>=r){
        sum[p]+=w;
        lazy[p]+=w;

        return ;
    }
    pushdown(p);
    int mid=(l+r)/2;
    if(ul<=mid)updatemul(p*2,l,mid,ul,ur,w);
    if(ur>mid)updatemul(p*2+1,mid+1,r,ul,ur,w);
}
int query(int p,int l,int r,int pos)//单点查询
{
    if(l==r){
        return sum[p];
    }
    pushdown(p);
    //printf("%d %d %d\n",l,r,sum[p]);
    int mid=(l+r)/2;
    if(pos<=mid)return query(p*2,l,mid,pos);
    else return query(p*2+1,mid+1,r,pos);
}
int main()
{
    int M;
    scanf("%d",&M);
    int n=0;
    for(int i=0;i<M;i++){
        int op,pos,w;
        scanf("%d",&op);
        b[i].op=op;
        if(op==1){
            scanf("%d",&pos);
            b[i].pos=pos;
            n++;
            edge[pos].push_back(n);
        }else if(op==2){
            scanf("%d%d",&pos,&w);
            b[i].pos=pos,b[i].w=w;
        }else{
            scanf("%d",&pos);
            b[i].pos=pos;
        }
    }
    dfs(0);
    n=0;
    for(int i=0;i<M;i++){
        if(b[i].op==1){
            updateone(1,1,id,vis[++n]);
        }else if(b[i].op==2){
            updatemul(1,1,id,vis[b[i].pos],vis[b[i].pos]+siz[b[i].pos],b[i].w);
        }else {
            printf("%d\n",query(1,1,id,vis[b[i].pos]));
        }
    }
    return 0;
}