1 条题解

  • 3
    @ 2023-7-27 14:18:25

    image

    #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
    上传者