#线段树 #树状数组 #dfn序

题意

• n个结点，n-1条边
• 给定根k和每个点的权值v_i
• 有m个操作，两种
  • 1 a x 将结点a的权值+x
  • 2 a 求a节点所在的子树的所有结点的权值和

思路

• 用dfn把树转化成链
• 线段树or树状数组维护单点修改区间查询

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int v[1010101];
vector<int> G[1010101];

int tim;
int L[4040404],R[4040404],dfn[4040404];
long long t[4040404];

void dfs(int x,int fa){
    L[x]=++tim;
    dfn[tim]=x;
    for(auto i:G[x]){
        if(i==fa)continue;
        dfs(i,x);
    }
    R[x]=tim;
}


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

void add(int p,int l,int r,int pos,int num){
    if(l==r){
        t[p]+=num;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) add(p*2,l,mid,pos,num);
    else add(p*2+1,mid+1,r,pos,num);
    t[p]=t[p*2+1]+t[p*2];
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m,k;
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) cin >> v[i] ;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(k,0);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op;
        cin >> op;
        if(op==1){
            int a,x;
            cin >> a >> x;
            add(1,1,n,L[a],x);
        }else{
            int a;
            cin >> a;
            cout << cal(1,1,n,L[a],R[a]) << endl;
        }
    }
    return 0;
}