#线段树 #树状数组 #dfn

题意

• n个结点，n-1条边，根为1
• 给定每个点的权值v_i
• 有m个操作，两种
  • 1 a x 将结点a的权值+x，结点a的儿子权值-x，结点a的孙子权值+x，以此类推
  • 2 a 求a节点的权值

思路

• 对于每一个点的修改，在这个点的子树中，所有和它奇偶性相同的点操作是+，所有和它奇偶性不同的点操作是相反的
• 可以维护两个线段树，一个维护深度为奇数的点，一个维护深度为偶数的点
• 对于每次修改在两颗树上同步维护就行
• 对于每次查询根据查询点的奇偶性单独输出即可
• 线段树只维护变化量，最后输出加上初始值就行，避免建树初始化
• 另一个思路是维护差分树状数组，代码量较小
• 附一个差分树状数组的blog

代码

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

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

int tim;
int L[202020],R[202020],dfn[202020];
int dep[202020];
long long t[2][1010101];

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

void pushdown(int p,int flg){
    t[flg][p*2]+=t[flg][p];
    t[flg][p*2+1]+=t[flg][p];
    t[flg][p]=0;
}

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

long long cal(int p,int l,int r,int x,int flg){
    if(l==r){
        return t[flg][p];
    }
    if(t[flg][p]!=0) pushdown(p,flg);
    int mid=(l+r)>>1;
    if(x>mid) return cal(p*2+1,mid+1,r,x,flg);
    else return cal(p*2,l,mid,x,flg);
}

int 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=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    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],R[a],x,dep[a]&1);
            add(1,1,n,L[a],R[a],-x,!(dep[a]&1));
        }else{
            int a;
            cin >> a;
            cout << cal(1,1,n,L[a],dep[a]&1)+v[a] << endl;
        }
    }
    return 0;
}