C. Propagating tree

本文主要是介绍C. Propagating tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://codeforces.com/contest/383/problem/C

因为是单点查询，操作一是+-+-

可以分奇偶性考虑

奇数 +-+-, -+-+

偶数  +-+,   -+-

我们可以发现奇数和偶数的标记是相反的

因此我们维护奇数点的标记，如果点是奇数就+val,否者就-val

查询的时候奇数点直接+a[u]，偶数点相反再+a[u]

code

// Problem: C. Propagating tree
// Contest: Codeforces - Codeforces Round 225 (Div. 1)
// URL: https://codeforces.com/problemset/problem/383/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=2e5+9;
int a[N],fa[N],sz[N],wc[N],dep[N],dfn[N],rdfn[N],top[N];
int n,m,r,p,vistime;
vector<int> e[N<<1];
void add(int u,int v){e[u].push_back(v);e[v].push_back(u);
}
void dfs1(int u,int f){fa[u]=f;sz[u]=1;dep[u]=dep[f]+1;for(auto & i : e[u]){if(i!=f){dfs1(i,u);sz[u]+=sz[i];if(sz[i]>sz[wc[u]]){wc[u]=i;}}}
}
void dfs2(int u,int Top){dfn[u]=++vistime;rdfn[vistime]=u;top[u]=Top;if(wc[u]){dfs2(wc[u],Top);for(auto & i : e[u]){if(i!=wc[u] && i!=fa[u]){dfs2(i,i);}   }}
}
struct node{ll val,tag;
}seg[N<<2];
ll tl(ll x){return x<<1;
}
ll tr(ll x){return x<<1|1;
}
void pushup(int id){seg[id].val=(seg[tl(id)].val+seg[tr(id)].val);
}
bool inrange(int L,int R,int l,int r){return L>=l && R<=r;
}
bool outofrange(int L,int R,int l,int r){return  L>r || l>R;
}
void maketag(int id,int l,int r,ll v){(seg[id].val+=(r-l+1)*v);(seg[id].tag+=v);
}
void pushdown(int id,int l,int r){int mid=(l+r)>>1;maketag(tl(id),l,mid,seg[id].tag);  maketag(tr(id),mid+1,r,seg[id].tag);seg[id].tag=0;  
}
ll query(int id,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[id].val;}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);return (query(tl(id),L,mid,l,r)+query(tr(id),mid+1,R,l,r));}else{return 0;}
}
void modify(int id,int L,int R,int l,int r,ll v){if(inrange(L,R,l,r)){maketag(id,L,R,v);}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);modify(tl(id),L,mid,l,r,v);modify(tr(id),mid+1,R,l,r,v);pushup(id);}
}
ll ask(int id,int l,int r,int pos){if(l==r){return seg[id].val;}int mid=(l+r)>>1;pushdown(id,l,r);if(mid>=pos){return ask(tl(id),l,mid,pos);}else{return ask(tr(id),mid+1,r,pos);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;add(u,v);}//root=1dfs1(1,0);dfs2(1,0);for(int i=1;i<=m;i++){int op;cin>>op;if(op==1){int x,val;cin>>x>>val;val*=(dep[x]&1?1:-1);modify(1,1,n,dfn[x],dfn[x]+sz[x]-1,val);}else{int x;cin>>x;ll ans=ask(1,1,n,dfn[x]);ans*=(dep[x]&1?1:-1);ans+=a[x];cout<<ans<<'\n';}}return 0;
}

这篇关于C. Propagating tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---