CF383C

很久以前，有一棵神橡树(oak)，上面有$n$个节点，从$1$~$n$编号，由$n-1$条边相连。它的根是$1$号节点。

这棵橡树每个点都有一个权值，你需要完成这两种操作：
$1$ $u$ $val$ 表示给$u$节点的权值增加$val$
$2$ $u$ 表示查询$u$节点的权值

但是这不是普通的橡树，它是神橡树。
所以它还有个神奇的性质：当某个节点的权值增加$val$时，它的子节点权值都增加$-val$，它子节点的子节点权值增加$-(-val)$…… 如此一直进行到树的底部。

思路

看到这个性质很容易想到就想到深度的奇偶性。

操作一进行时会修改对应的子树，于是想到了 dfs 序。

这个性质又该如何操作呢？

考虑建两个线段树，一个存放深度为奇数的点，一个存放深度为偶数的点，操作一个点时判断一下其深度再操作即可。

如此就转化为了一个轻松的区间加减，单点查询的问题。

操作一，奇偶性相同加，不同减；操作二根据深度直接查询。

代码

#include<bits/stdc++.h>
#define N 200010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m,a[N];

int head[N],tot=0;
struct graph{
    int v,next;
}edge[N<<1];
void add_edge(int u,int v) {edge[++tot].v=v,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}

int depth[N],fa[N],size_0[N],size[N],id[N],cnt=0,rk[N];
void dfs(int u) {
    depth[u]=depth[fa[u]]+1;
    size[u]=1;
    id[u]=++cnt;
    rk[cnt]=u;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs(v);
        size[u]+=size[v];
    }
}

class SegmentTree{
  private:
    int sum[N<<2],lazy[N<<2];
    #define s(x) sum[x]
    #define l(x) lazy[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
    void spread(int p,int l,int r) {
        if(!l(p)) return ;
        s(ls)+=(mid-l+1)*l(p),l(ls)+=l(p);
        s(rs)+=(r-mid)*l(p),l(rs)+=l(p);
        l(p)=0;
    }
  public:
    void modify(int p,int l,int r,int x,int y) {
        if(l>x||r<x) return ;
        if(l==r) {
            s(p)=y;
            return ;
        }
        modify(ls,l,mid,x,y),modify(rs,mid+1,r,x,y);
        update(p);
    }
    void modify(int p,int l,int r,int L,int R,int x) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            s(p)+=(r-l+1)*x;
            l(p)+=x;
            return ;
        }
        spread(p,l,r);
        modify(ls,l,mid,L,R,x),modify(rs,mid+1,r,L,R,x);
        update(p);
    }
    int ask(int p,int l,int r,int x) {
        if(l>x||r<x) return 0;
        if(l==r) return s(p);
        spread(p,l,r);
        return ask(ls,l,mid,x)+ask(rs,mid+1,r,x);
    }
}SMT[2];

void init() {
    dfs(1);
    for(int i=1;i<=n;i++) {
        if(depth[i]&1) SMT[1].modify(1,1,n,id[i],a[i]);
        else SMT[0].modify(1,1,n,id[i],a[i]);
    }
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++) {
        int u=read(),v=read();
        add(u,v);
    }

    init();
    for(int i=1;i<=m;i++) {
        int op,u,v,val;
        op=read();
        if(op==1) {
            v=read(),val=read();
            if(depth[v]&1) {
                SMT[1].modify(1,1,n,id[v],id[v]+size[v]-1,val);
                SMT[0].modify(1,1,n,id[v],id[v]+size[v]-1,-val);
            }
            else {
                SMT[0].modify(1,1,n,id[v],id[v]+size[v]-1,val);
                SMT[1].modify(1,1,n,id[v],id[v]+size[v]-1,-val);
            }
        }
        else {
            u=read();
            printf("%d\n",(depth[u]&1?SMT[1].ask(1,1,n,id[u]):SMT[0].ask(1,1,n,id[u])));
        }
    }
    system("pause");
    return 0;
}