首页 > 代码库 > CodeForces - 383C Propagating tree(dfs + 线段树)
CodeForces - 383C Propagating tree(dfs + 线段树)
题目大意:
给出一棵树,树上每个节点都有权值,然后有两个操作。
1 x val 在结点x上加上一个值val,x的儿子加上 -val,x的儿子的儿子加上 - (-val),以此类推。
2 x 问x节点的值。
思路分析:
每个节点上加值都是给自己的儿子节点加,而且这个是颗树。
比如样例上的,如果你给node 1加一个值,那么五个节点都加。
再给node 2加个值,2的儿子节点也加了,之前给1加的值也要加到2号节点的儿子。
所以你会发现节点的儿子会存在一个从属的关系。
这样的话,我们可以把所有节点从新编号。然后记录一下这个节点能更新哪个区间。然后就是简单的线段树了。
再说一下加法的合并。每一个操作都记录这个操作的节点的深度,然后合并的时候再考虑一下深度是如何合并的就好了。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 200005 #define maxm 1000005 #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e using namespace std; int tot; int a[maxn]; int head[maxm],to[maxm],next[maxm]; int num[maxn],ed[maxn],dep[maxn],rev[maxn]; int res[maxn<<2]; int add[maxn<<2]; int cov[maxn<<2]; int Abs(int x) { return x>0?x:-x; } void pushdown(int num,int s,int e) { if(cov[num]) { if(!cov[num<<1])cov[num<<1]=cov[num],add[num<<1]=add[num]; else { if(Abs(cov[num<<1]-cov[num])&1)add[num<<1]+=-add[num]; else add[num<<1]+=add[num]; } if(!cov[num<<1|1])cov[num<<1|1]=cov[num],add[num<<1|1]=add[num]; else { if(Abs(cov[num<<1|1]-cov[num])&1)add[num<<1|1]+=-add[num]; else add[num<<1|1]+=add[num]; } cov[num]=0,add[num]=0; } } void build(int num,int s,int e) { cov[num]=0; add[num]=0; if(s==e) { res[num]=a[rev[s]]; return; } int mid=(s+e)>>1; build(lson); build(rson); } void update(int num,int s,int e,int l,int r,int dp,int val) { if(l<=s && r>=e) { if(!cov[num]) { cov[num]=dp; add[num]=val; } else { if(Abs(cov[num]-dp)&1)add[num]+=-val; else add[num]+=val; } return; } int mid=(s+e)>>1; pushdown(num,s,e); if(l<=mid)update(lson,l,r,dp,val); if(r>mid)update(rson,l,r,dp,val); } int query(int num,int s,int e,int pos) { if(s==e) { if(cov[num]) { if(Abs(cov[num]-dep[s])&1)res[num]+=-add[num]; else res[num]+=add[num]; cov[num]=0,add[num]=0; } return res[num]; } int mid=(s+e)>>1; pushdown(num,s,e); if(pos<=mid)return query(lson,pos); else return query(rson,pos); } void addedge(int u,int v) { tot++; to[tot]=v; next[tot]=head[u]; head[u]=tot; } int cnt=0; bool vis[maxn]; int dfs(int x,int dp) { num[x]=++cnt; dep[num[x]]=dp; int d=num[x]; for(int p=head[x]; p; p=next[p]) { if(vis[to[p]])continue; vis[to[p]]=true; d=max(d,dfs(to[p],dp+1)); } ed[num[x]]=d; return ed[num[x]]; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&a[i]); tot=0; memset(head,0,sizeof head); for(int i=1; i<n; i++) { int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } memset(vis,false,sizeof vis); vis[1]=true,dep[1]=1; dfs(1,1); for(int i=1; i<=cnt; i++) { rev[num[i]]=i; } build(1,1,cnt); while(m--) { int op; scanf("%d",&op); if(op==1) { int x,val; scanf("%d%d",&x,&val); if(num[x]>ed[num[x]])update(1,1,cnt,ed[num[x]],num[x],dep[num[x]],val); else update(1,1,cnt,num[x],ed[num[x]],dep[num[x]],val); } else { int x; scanf("%d",&x); printf("%d\n",query(1,1,cnt,num[x])); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。