Change FZU - 2277（线段树+dfs序）
本文共 4154 字，大约阅读时间需要 13 分钟。
There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.
Initially all the node’s value is 0.
We have q operations. There are two kinds of operations.
1 v x k : a[v]+=x , a[v’]+=x-k (v’ is child of v) , a[v’’]+=x-2*k (v’’ is child of v’) and so on.
2 v : Output a[v] mod 1000000007(10^9 + 7).
Input
First line contains an integer T (1 ≤ T ≤ 3), represents there are T test cases.In each test case:
The first line contains a number n.
The second line contains n-1 number, p2,p3,…,pn . pi is the father of i.
The third line contains a number q.
Next q lines, each line contains an operation. (“1 v x k” or “2 v”)
1 ≤ n ≤ 3*10^5
1 ≤ pi < i
1 ≤ q ≤ 3*10^5
1 ≤ v ≤ n; 0 ≤ x < 10^9 + 7; 0 ≤ k < 10^9 + 7
Output
For each operation 2, outputs the answer.Sample Input
1 3 1 1 3 1 1 2 1 2 1 2 2 Sample Output 2 1 这个题目的出奇之处就是在更新的时候，每个点的更新多少是不一样的。
我们看题干这里，每个节点更新的是随着深度的增加逐渐递减的，我们必须找出这之间的规律才能做。假如树的祖先深度是deep[v]，那么它的一个子节点u的深度是deep[u]，子节点更新的值是 x-(deep[u]-deep[v])*k。对于v所有的子树来说，都会更新的值是x+deep[v]*k。剩下的就和自己的深度有关了。那么我们线段树维护两个lazy，一个记录都增加的值，另一个就记录k。 代码如下： #include#include #include #include #include #define ll unsigned long long#define mod 1000000007 using namespace std;const int maxx=3e5+100;struct node{ int l; int r; ll lazy1; ll lazy2; ll sum;}p[maxx<<2];struct edge{ int to; int next;}e[maxx];int deep[maxx],in[maxx],out[maxx],pre[maxx],head[maxx<<1];int tot,sign,n,m;/*----------------事前准备---------------*/ inline void init(){ memset(head,-1,sizeof(head)); tot=sign=0;}inline void read(int &x)//快速读入{ int f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){ if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){ x=x*10+s-'0';s=getchar();} x*=f;}void read1(ll &x){ int f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){ if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){ x=x*10+s-'0';s=getchar();} x*=f;}inline void add(int u,int v){ e[tot].to=v,e[tot].next=head[u],head[u]=tot++;}/*--------------dfs---------------*/inline void dfs(int u,int f){ deep[u]=deep[f]+1; in[u]=++sign; pre[sign]=u; for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; if(to==f) continue; dfs(to,u); } out[u]=sign;}/*-----------------线段树-----------------*/inline void pushdown(int cur){ if(p[cur].lazy1) { p[cur<<1].lazy1+=p[cur].lazy1; p[cur<<1].lazy1%=mod; p[cur<<1|1].lazy1+=p[cur].lazy1; p[cur<<1|1].lazy1%=mod; p[cur<<1].sum=(p[cur<<1].sum+p[cur].lazy1*(p[cur<<1].r-p[cur<<1].l+1)%mod+mod)%mod; p[cur<<1|1].sum=(p[cur<<1|1].sum+p[cur].lazy1*(p[cur<<1|1].r-p[cur<<1|1].l+1)%mod+mod)%mod; p[cur].lazy1=0; } if(p[cur].lazy2) { p[cur<<1].lazy2+=p[cur].lazy2; p[cur<<1].lazy2%=mod; p[cur<<1|1].lazy2+=p[cur].lazy2; p[cur<<1|1].lazy2%=mod; p[cur].lazy2=0; }}inline void build(int l,int r,int cur){ p[cur].l=l; p[cur].r=r; p[cur].lazy1=p[cur].lazy2=p[cur].sum=0; if(l==r) return ; int mid=l+r>>1; build(l,mid,cur<<1); build(mid+1,r,cur<<1|1);}inline void update(int l,int r,ll v,ll k,int cur){ int L=p[cur].l; int R=p[cur].r; if(l<=L&&R<=r) { p[cur].sum=(p[cur].sum+v*(R-L+1)%mod+mod)%mod; p[cur].lazy1=(p[cur].lazy1+v+mod)%mod; p[cur].lazy2=(p[cur].lazy2+k+mod)%mod; return ; } pushdown(cur); int mid=L+R>>1; if(r<=mid) update(l,r,v,k,cur<<1); else if(l>mid) update(l,r,v,k,cur<<1|1); else { update(l,mid,v,k,cur<<1); update(mid+1,r,v,k,cur<<1|1); }}inline ll query(int pos,int cur){ int L=p[cur].l; int R=p[cur].r; if(L==R) return (p[cur].sum+deep[pre[L]]*p[cur].lazy2%mod+mod)%mod;//到达所要求的节点的时候，不要忘了加上和这个点深度有关的那一部分值。 pushdown(cur); int mid=L+R>>1; if(pos<=mid) return query(pos,cur<<1); else return query(pos,cur<<1|1);}int main(){ int t,x,op; ll v,k; read(t); while(t--) { init(); read(n); for(int i=2;i<=n;i++) { read(x); add(i,x); add(x,i); } deep[0]=-1; dfs(1,0); build(1,n,1); read(m); while(m--) { read(op); if(op==1) { read(x);read1(v);read1(k); update(in[x],out[x],deep[x]*k+v,-k,1); } else if(op==2) { read(x); printf("%I64d\n",query(in[x],1)); } } } return 0;}
努力加油a啊，(o)/~
转载地址：http://cztvi.baihongyu.com/
你可能感兴趣的文章