題意:
給你一棵n個結點的樹, 以1為根。每個結點有點權。有m次操作:
1.x結點權值 +val,x的兒子權值 −val,x的孫子們 +val,以此類推。
2.詢問x的點權;
題解:
我們首先跑一邊dfs序,順便求除每個結點的深度。
我們把他分成兩顆線段樹,深度為奇數的在第一顆上,深度為偶數的在第二課上。
我們每次對兩顆線段樹同時操作。
第一顆線段樹隻進行+操作,第二棵線段樹隻-操作。
當我們詢問某個點時,我們隻需要判斷一下這個點的奇偶,決定查詢哪顆樹即可。
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =4e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
vector<int> edge[maxn];
int a[maxn];
int in[maxn],out[maxn],cnt;
int tree[2][maxn<<2];
int deep[maxn];
void dfs(int u,int fa){
in[u]=++cnt;
deep[u]=deep[fa]+1;
for(auto i:edge[u]){
if(i==fa) continue;
dfs(i,u);
}
out[u]=cnt;
}
void push(int node,int x){
if(tree[x][node]){
tree[x][node*2]+=tree[x][node];
tree[x][node*2+1]+=tree[x][node];
tree[x][node]=0;
}
return;
}
void update(int node,int l,int r,int start,int ends,int x,int val){
if(start<=l&&ends>=r){
tree[x][node]+=val;
//cout<<tree[x][node]<<endl;
return;
}
push(node,x);
int mid=(l+r)/2;
if(start<=mid) update(node*2,l,mid,start,ends,x,val);
if(mid<ends) update(node*2+1,mid+1,r,start,ends,x,val);
}
int query(int node,int l,int r,int pos,int x){
if(l==r){
//cout<<tree[x][node]<<endl;
return tree[x][node];
}
push(node,x);
int mid=(l+r)/2;
if(pos<=mid) return query(node*2,l,mid,pos,x);
else return query(node*2+1,mid+1,r,pos,x);
}
signed main(){
//
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1,0);
//for(int i=1;i<=n;i++) cout<<in[i]<<" ";
for(int i=0;i<m;i++){
int opt,x,y;
cin>>opt;
if(opt==1){ //246 296
cin>>x>>y;
//cout<<in[x]<<" "<<out[x]<<endl;
update(1,1,n,in[x],out[x],deep[x]&1,y);
update(1,1,n,in[x],out[x],!(deep[x]&1),-y);
}
else{
cin>>x;
cout<<query(1,1,n,in[x],deep[x]&1)+a[x]<<endl;
}
}
return 0;
}