线段树|FZU - 2277(树链剖分或dfs序+线段树) 线段树|图论

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
【线段树|FZU - 2277(树链剖分或dfs序+线段树)】1?≤?pi? 1?≤?q?≤?3*10^5
1?≤?v?≤?n; 0?≤?x? 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

看了网上的题解博客，弄懂思路，经过不断调试和修改，终于在规定时间ac了。
思路：
树链剖分。
用dfs序分割出每一颗子树，编号自动从1到n，不用操作，在一条链上的点都是连续的，而且可以一一对应到线段树上，因为题目刚开始没有初始值，所以也不用建树，最后的查询也不是对某一条链进行查询，直接是单点查询，所以，应该也称不上熟练剖分吧，都说是dfs序+线段树。
总之还是dfs序好些，以后再写一写熟练剖分的代码吧。
代码：

#include #include #include #include #define lson rt1<<1,l,m #define rson rt1<<1|1,m+1,r #define LL long long using namespace std; const LL maxn=310000; const LL mod=1e9+7; vectorG[maxn]; LL deep[maxn]; LL st[maxn],en[maxn]; LL ans=0; LL tem=0; //**************** LL sum[maxn*4],sumk[maxn*4]; void dfs(LL x) { deep[x]=ans; st[x]=tem++; ans++; for(LL i=0; i>1; if(lt<=m)update(u,x,k,lt,rt,lson); if(rt>m)update(u,x,k,lt,rt,rson); } LL quert(LL u,LL L,LL R,LL rt1,LL l,LL r) { if(L<=l&&r<=R) { return (sum[rt1]-(sumk[rt1]*deep[u])%mod)%mod; } LL m=(l+r)>>1; if(L<=m)return(quert(u,L,R,lson)+sum[rt1]-(sumk[rt1]*deep[u])%mod)%mod; else return(quert(u,L,R,rson)+sum[rt1]-(sumk[rt1]*deep[u])%mod)%mod; } int main() { LL t; scanf("%I64d",&t); while(t--) { memset(deep,0,sizeof(deep)); memset(sum,0,sizeof(sum)); memset(sumk,0,sizeof(sumk)); memset(st,0,sizeof(st)); memset(en,0,sizeof(en)); ans=0,tem=1; LL n; scanf("%I64d",&n); for(int i=1; i<=n; i++)G[i].clear(); LL u; for(int i=2; i<=n; i++) { scanf("%I64d",&u); G[u].push_back(i); } LL m,f,x,k; LL lt,rt; scanf("%I64d",&m); ans=0; dfs(1); while(m--) {scanf("%I64d",&f); if(f==1) { scanf("%I64d%I64d%I64d",&u,&x,&k); lt=st[u]; rt=en[u]; update(u,x,k,lt,rt,1,1,n); } else { scanf("%I64d",&u); lt=st[u]; rt=st[u]; printf("%I64d\n",(quert(u,lt,rt,1,1,n)+mod)%mod); } } } return 0; }