Propagating tree(奇偶性+dfs序+差分线段树)

题目大意：
给你一颗树，你可以在树上进行两种操作
1 x val,把val加到x节点上面去，然后-val加到x的第一层儿子节点，然后-(-val)加到第二层儿子节点，。。。等
2 x,查询x节点的值。
思路：
这题看了大佬的思路才做出来的。

https://blog.nowcoder.net/n/d8f8de427aae4b65a43bf5383a75938b

这个题的关键就是先把每个节点是奇数层还是偶数层求出来，然后求一个dfs序，把每个节点为子树的儿子节点的范围求出来。
对于1操作，该节点能够影响的范围有[l[x],r[x]]，那么对这个区间做一个加法，我们可以用线段树或者树状数组差分来实现s[l[x]]+=v,s[r[x]+1]-=v;
对于2操作，该节点x的值=w[i]+(奇)[1,l[x]]-(偶)[1,l[x]]。
所以我们可以通过维护两颗线段树(维护奇数层和偶数层)来实现。
代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 4e5 + 10;
vector<int>G[maxn];
int in[maxn],out[maxn],tot;
bool cal[maxn];
int w[maxn];
void dfs(int u,int fu,int dep){
    in[u] = ++tot;cal[u] = dep % 2;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs(v,u,dep + 1);
        }
    }
    out[u] = tot;
}
#define lson (rt * 2)
#define rson (rt * 2) + 1
#define mid (l + r) / 2
struct seg{
    int s[maxn << 2];
    void update(int l,int r,int pos,int rt,int v){
        if(l == r){
            s[rt] += v;
            return ;
        }
        if(pos <= mid)update(l,mid,pos,lson,v);
        else update(mid + 1,r,pos,rson,v);
        s[rt] = s[lson] + s[rson];
    }
    int query(int l,int r,int ql,int qr,int rt){
        if(l >= ql && r <= qr){
            return s[rt];
        }
        int ans = 0;
        if(ql <= mid)ans += query(l,mid,ql,qr,lson);
        if(qr > mid)ans += query(mid + 1,r,ql,qr,rson);
        return ans;
    }
}tree[2];
void solved(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)scanf("%d",&w[i]);
    for(int i = 1; i < n; i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0,1);
    ++tot;
    while(m--){
        int ins;scanf("%d",&ins);
        if(ins == 1){
            int x,v;scanf("%d%d",&x,&v);
            tree[cal[x]].update(1,tot,in[x],1,v);
            tree[cal[x]].update(1,tot,out[x] + 1,1,-v);
        }else{
            int x;scanf("%d",&x);
            printf("%d\n",w[x] + tree[cal[x]].query(1,tot,1,in[x],1) - tree[cal[x] ^ 1].query(1,tot,1,in[x],1));
        }
    }
}
int main(){
    solved();
    return 0;
}