1 条题解
-
3
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=200005; int n,m,k,s,t,tot,dfn[N],sz[N],de[N],w[N]; vector<int> e[N]; ll a[N],b[N]; //a 奇 b 偶 void dfs(int u,int fa){ sz[u]=1;dfn[u]=++tot; for (int &v:e[u]){ if (v==fa) continue; de[v]=de[u]+1; dfs(v,u); sz[u]+=sz[v]; } } void add(ll a[],int l,int r,int x){ for (int i=l;i<=n;i+=i&(-i)) a[i]+=x; for (int i=r;i<=n;i+=i&(-i)) a[i]-=x; } ll query(ll a[],int l){ ll ans=0; for (int i=l;i;i-=i&(-i)) ans+=a[i]; return ans; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for (int i=1;i<=n;++i) cin>>w[i]; for (int i=1;i<n;++i){ cin>>s>>t; e[s].push_back(t); e[t].push_back(s); } dfs(1,0); int opt,u,x; for (int i=1;i<=m;++i){ cin>>opt>>u; if (opt==1) { cin>>x; add(a,dfn[u],dfn[u]+sz[u],(de[u]&1?x:-x)); add(b,dfn[u],dfn[u]+sz[u],(de[u]&1?-x:x)); } else { if (de[u]&1) cout<<query(a,dfn[u])+w[u]<<"\n"; else cout<<query(b,dfn[u])+w[u]<<"\n"; } } }
- 1
信息
- ID
- 348
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 27
- 已通过
- 22
- 上传者