Codeforces 384E-线段树+dfs序

如果这题只传到儿子不继续向下就是裸的dfs序+线段树，继续往下传的还改变正负号，我们可以根据它的层数来确定正负号

 #include<bits/stdc++.h>

 #define inf 0x3f3f3f3f

 #define lson (id<<1)

 #define rson ((id<<1)|1)

 #define mid ((l+r)>>1)

 const int maxn=;

 using namespace std;

 int t;

 int p;

 int n,m;

 int u,v;

 int x,val;

 int dep[maxn+];

 int a[maxn+];

 int pos[maxn+];

 int q[maxn+];

 int son[maxn+];

 int tree[maxn*+];

 int sum[maxn*+];

 int lazy[maxn*+];

 vector<int> G[maxn+];

 void push_up(int id){

    tree[id]=tree[lson]+tree[rson];

 }

 void push_down(int id,int l,int r){

         if(lazy[id]){

                 lazy[lson]+=lazy[id];

                 lazy[rson]+=lazy[id];

                 tree[lson]+=(mid-l+)*lazy[id];

                 tree[rson]+=(r-mid)*lazy[id];

                 lazy[id]=;

         }

         return ;

 }

 void build(int id,int l,int r){

       if(l==r){

         sum[id]=a[pos[l]];

         return ;

       }

       build(lson,l,mid);

       build(rson,mid+,r);

       push_up(id);

       return ;

 }

 void update(int id,int l,int r,int x,int y,int val){

         if(l==x&&r==y){

                 tree[id]+=val*(r-l+);

                 lazy[id]+=val;

                 return ;

         }

         push_down(id,l,r);

         if(x>mid){

                 update(rson,mid+,r,x,y,val);

         } else if(y<=mid){

                 update(lson,l,mid,x,y,val);

         } else {

                 update(lson,l,mid,x,mid,val);

                 update(rson,mid+,r,mid+,y,val);

         }

 }

 int fi(int id,int l,int r,int x){

         if(l==r){

                 int temp=dep[pos[l]]&;

                 if(!temp) temp=-;

                 return sum[id]+lazy[id]*temp;

         }

         push_down(id,l,r);

         if(x<=mid){

                 return fi(lson,l,mid,x);

         } else {

                 return fi(rson,mid+,r,x);

         }

 }

 void dfs(int x,int fa,int d){

         dep[x]=d;

         pos[++p]=x;

         q[x]=p;

         for(size_t i=;i<G[x].size();i++){

                 if(G[x][i]==fa) continue;

                 dfs(G[x][i],x,d+);

                 son[x]++;

                 son[x]+=son[G[x][i]];

         }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

     }

     for(int i=;i<n;i++){

         scanf("%d%d",&u,&v);

         G[u].push_back(v);

         G[v].push_back(u);

     }

     dfs(,,);

     build(,,n);

     for(int i=;i<=m;i++){

         scanf("%d",&t);

         if(t==){

         scanf("%d%d",&x,&val);

         if(dep[x]&)

         update(,,n,q[x],q[x]+son[x],val);

         else update(,,n,q[x],q[x]+son[x],-val);

         } else {

         scanf("%d",&x);

         int ans=fi(,,n,q[x]);

         printf("%d\n",ans);

         }

     }

     return ;

 }