Time Limit: 2000 mSec Memory Limit : 262144 KB
Problem Description
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
3
1 1
3
1 1 2 1
2 1
2 2
Sample Output
1
Source
第八届福建省大学生程序设计竞赛-重现赛（感谢承办方厦门理工学院）
lld wa一天
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define LL __int64
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x) cout<<"bug"<<x<<endl;
const int N=3e5+,M=2e6+,inf=1e9+;
const LL INF=1e18+,mod=1e9+; struct isss
{
int v,nex;
}edge[N<<];
int head[N],edg;
int in[N],out[N],tot;
LL deep[N];
void add(int u,int v)
{
++edg;
edge[edg].v=v;
edge[edg].nex=head[u];
head[u]=edg;
}
void dfs(int u,int fa,int dp)
{
in[u]=++tot;
deep[u]=dp;
for(int i=head[u];i;i=edge[i].nex)
{
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u,dp+);
}
out[u]=tot;
}
struct AYT
{
LL tree[N];
void init()
{
memset(tree,,sizeof(tree));
}
int lowbit(int x)
{
return x&-x;
}
void update(int x,LL c)
{
while(x<N)
{
tree[x]+=c;
x+=lowbit(x);
}
}
LL query(int x)
{
LL ans=;
while(x)
{
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
}TX,TK; void init()
{
tot=;
memset(head,,sizeof(head));
memset(deep,,sizeof(deep));
TX.init();
TK.init();
edg=;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
init();
for(int i=;i<=n;i++)
{
int f;
scanf("%d",&f);
add(f,i);
add(i,f);
}
dfs(,-,);
int q;
scanf("%d",&q);
while(q--)
{
int t,v;
LL x,k;
scanf("%d%d",&t,&v);
if(t==)
{
scanf("%I64d%I64d",&x,&k);
x+=1LL*deep[v]*k;
x%=mod;
TX.update(in[v],x);
TX.update(out[v]+,-x);
TK.update(in[v],k);
TK.update(out[v]+,-k);
}
else
{
LL xx=TX.query(in[v]);
LL y=TK.query(in[v]);
y%=mod;
LL ans=xx-1LL*deep[v]*y;
ans%=mod;ans+=mod;ans%=mod;
printf("%I64d\n",ans);
}
}
}
return ;
}