#dfs序 #线段树

题意

• 1为根的树，n个节点，每个点有点权
• 处理m个操作，操作有三种
  1. 给某个点的点权+a
  2. 给某个点的的子树中所有结点点权+a
  3. 询问结点x到根的路径上所有点的权值和

思路

• 前两个操作都好处理，借助dfn序把树变为线性结构即可
• 对于询问，dfn无法直接解决到根的路径和，可以考虑对dfs序操作
• dfs序中每个元素出现两次，第一次出现记为+第二次出现记为-
• 路径和就是dfs序中当前这个点第一次出现的前缀和，线段树维护即可
• 线段树还得维护区间中+的个数，以保证lazy的传递

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
int v[202020];
vector<int> G[202020];
int l[202020],r[202020],dfs_idx[202020],flg[202020];
int tim;
int t[808080],cnt[808080],laz[808080];


void dfs(int x,int fa){
    l[x]=++tim;
    dfs_idx[tim]=x;
    flg[tim]=1;
    for(auto i:G[x]){
        if(i==fa) continue;
        dfs(i,x);
    }
    r[x]=++tim;
    dfs_idx[tim]=x;
    flg[tim]=-1;
}


void pushup(int p){
    t[p]=t[p*2]+t[p*2+1];
    cnt[p]=cnt[p*2]+cnt[p*2+1];
}

void build(int p,int l,int r){
    if(l==r){
        t[p]=v[dfs_idx[l]]*flg[l];
        cnt[p]=(flg[l]>0);
        return ;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}

void pushdown(int p,int l,int r){
    int mid=(r+l)>>1;
    t[p*2]+=cnt[p*2]*laz[p]-(mid-l+1-cnt[p*2])*laz[p];
    t[p*2+1]+=cnt[p*2+1]*laz[p]-(r-mid-cnt[p*2+1])*laz[p];
    laz[p*2]+=laz[p];
    laz[p*2+1]+=laz[p];
    laz[p]=0;
}

void add(int p,int l,int r,int x,int y,int num){
    if(x<=l&&r<=y){
        laz[p]+=num;
        t[p]+=cnt[p]*num-(r-l+1-cnt[p])*num;
        return ;
    }
    if(laz[p]!=0) pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) add(p*2,l,mid,x,y,num);
    if(y>mid) add(p*2+1,mid+1,r,x,y,num);
    pushup(p);
}

int cal(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return t[p];
    }
    if(laz[p]!=0) pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(y<=mid) return cal(p*2,l,mid,x,y);
    if(x>mid) return cal(p*2+1,mid+1,r,x,y);
    return cal(p*2+1,mid+1,r,x,y)+cal(p*2,l,mid,x,y);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i];
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    build(1,1,tim);

    for(int i=1;i<=m;i++){
        int op;
        cin >> op;
        if(op==1){
            int x,a;
            cin >> x >> a;
            add(1,1,tim,l[x],l[x],a);
            add(1,1,tim,r[x],r[x],a);
        }else if(op==2){
            int x,a;
            cin >> x >> a;
            add(1,1,tim,l[x],r[x],a);
        }else{
            int x;
            cin >> x;
            cout << cal(1,1,tim,1,l[x]) << endl;
        }
    }
    return 0;
}