题面

题意

给出一棵树，每个点有一个点权，要求支持两种操作： 1.查询某个点的点权 2.子树加p，在子树中，与其深度的奇偶性相同的点加p，不同的点减p。

做法

因为在修改时会根据深度的奇偶性做出不同的修改，因此可以维护两棵线段树，一棵维护奇数深度的，另一棵维护偶数深度的，这样对于而操作只要在一棵树上加p，在另一棵树上减p即可。

代码

#include<iostream> #include<cstdio> #include<cstring> #define ll long long #define mid ((l+r)>>1) #define N 200100 using namespace std; int n,m,num[N],bb,first[N],in[N],out[N],ti,deep[N],dfn[N],ans; struct Bn { int to,next; }bn[N<<1]; struct Xds { int tt; struct Node { int ls,rs,sum; }; Node node[N<<1]; void init() { tt=1; } void build(int now,int l,int r) { if(l==r) { node[now].sum=num[dfn[l]]; return; } if(l<=mid) { node[now].ls=++tt; build(tt,l,mid); } if(mid<r) { node[now].rs=++tt; build(tt,mid+1,r); } } void add(int now,int l,int r,int u,int v,int w) { if(l==u&&v==r) { node[now].sum+=w; return; } if(u<=mid) { add(node[now].ls,l,mid,u,min(v,mid),w); } if(mid<v) { add(node[now].rs,mid+1,r,max(u,mid+1),v,w); } } void down(int now) { if(node[now].ls) { node[node[now].ls].sum+=node[now].sum; } if(node[now].rs) { node[node[now].rs].sum+=node[now].sum; } node[now].sum=0; } int ask(int now,int l,int r,int u) { if(l==r) { return node[now].sum; } down(now); if(u<=mid) return ask(node[now].ls,l,mid,u); return ask(node[now].rs,mid+1,r,u); } }; Xds a,b; inline void ad(int u,int v) { bb++; bn[bb].to=v; bn[bb].next=first[u]; first[u]=bb; } void dfs(int now,int last) { int p,q; in[now]=++ti; dfn[ti]=now; for(p=first[now];p!=-1;p=bn[p].next) { if(bn[p].to==last) continue; deep[bn[p].to]=deep[now]+1; dfs(bn[p].to,now); } out[now]=ti; } int main() { memset(first,-1,sizeof(first)); int i,j,p,q,o; cin>>n>>m; for(i=1;i<=n;i++) { scanf("%d",&num[i]); } for(i=1;i<n;i++) { scanf("%d%d",&p,&q); ad(p,q),ad(q,p); } dfs(1,-1); a.init(); b.init(); a.build(1,1,n); b.build(1,1,n); for(i=1;i<=m;i++) { scanf("%d",&o); if(o==1) { scanf("%d%d",&p,&q); if(deep[p]&1) { a.add(1,1,n,in[p],out[p],q); b.add(1,1,n,in[p],out[p],-q); } else { b.add(1,1,n,in[p],out[p],q); a.add(1,1,n,in[p],out[p],-q); } } else { scanf("%d",&p); if(deep[p]&1) ans=a.ask(1,1,n,in[p]); else ans=b.ask(1,1,n,in[p]); printf("%d\n",ans); } } }