按深度染色，奇深度的点存反权值。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 vector <int> g[500005]; 5 int t1,t2,t3,seq[500005],a[1000005],s[500005],vis[500005],ind,n,m,src[500005],frm[500005],dep[500005]; 6 7 void dfs(int p) { 8 vis[p]=1; 9 frm[p]=ind+1; 10 for(int i=0;i<g[p].size();i++) 11 if(vis[g[p][i]]==0) 12 dep[g[p][i]]=dep[p]+1, 13 dfs(g[p][i]); 14 seq[p]=++ind; 15 } 16 17 void build(int p,int l,int r){ 18 if(l==r) a[p]=s[l]; 19 else build(p*2,l,(l+r)/2),build(p*2+1,(l+r)/2+1,r); 20 } 21 22 void modify(int p,int l,int r,int ql,int qr,int k){ 23 if(l>qr||r<ql) return; 24 if(l>=ql&&r<=qr) {a[p]+=k; return;} 25 a[p*2]+=a[p], a[p*2+1]+=a[p], a[p]=0; 26 modify(p*2,l,(l+r)/2,ql,qr,k); 27 modify(p*2+1,(l+r)/2+1,r,ql,qr,k); 28 } 29 30 int query(int p,int l,int r,int pos){ 31 if(l==r) return a[p]; 32 a[p*2]+=a[p], a[p*2+1]+=a[p], a[p]=0; 33 if(pos<=(l+r)/2) return query(p*2,l,(l+r)/2,pos); 34 else return query(p*2+1,(l+r)/2+1,r,pos); 35 } 36 37 int main(){ 38 ios::sync_with_stdio(false); 39 scanf("%d%d",&n,&m); 40 for(int i=1;i<=n;i++) scanf("%d",&src[i]); 41 for(int i=1;i<n;i++) scanf("%d%d",&t1,&t2), g[t1].push_back(t2), g[t2].push_back(t1); 42 dep[1]=1; dfs(1); 43 for(int i=1;i<=n;i++) dep[i]=-1+2*(dep[i]%2); 44 for(int i=1;i<=n;i++) s[seq[i]]=dep[i]*src[i]; 45 build(1,1,n); 46 for(int i=1;i<=m;i++) { 47 scanf("%d%d",&t1,&t2); 48 if(t1==1){ 49 scanf("%d",&t3); 50 modify(1,1,n,frm[t2],seq[t2],dep[t2]*t3); 51 } 52 else{ 53 printf("%d ",dep[t2]*query(1,1,n,seq[t2])); 54 } 55 } 56 return 0; 57 }