#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,p[100001],d[100001],q,h[100001],tin[100001],tout[100001],pos[100001],nxt[100001],t,res,lazy[400001];
vector <int> ke[100001];
vector <pair <int, int>> ke2[100001];
pair <int, int> mx[100001][2],st[400001];
void dfs(int u){
nxt[u]=u;
tin[u]=++t;
pos[t]=u;
mx[u][0]={d[u],u};
for (int v:ke[u]){
h[v]=h[u]+1;
d[v]+=d[u];
dfs(v);
ke2[u].push_back({tout[v],v});
if (mx[v][0]>mx[u][0]){
mx[u][1]=mx[u][0];
mx[u][0]=mx[v][0];
}
else
mx[u][1]=max(mx[u][1],mx[v][0]);
}
res=(res+mx[u][0].first+mx[u][1].first-d[u]*2)%mod;
nxt[mx[u][0].second]=u;
tout[u]=t;
}
void build(int node, int l, int r){
if (l==r){
st[node]={d[pos[l]],pos[l]};
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
st[node]=max(st[node<<1],st[node<<1|1]);
}
void update(int node, int l, int r, int u, int v, int val){
if (l>v||r<u||l>r||u>v)
return;
if (l>=u&&r<=v){
lazy[node]+=val;
st[node].first+=val;
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,u,v,val);
update(node<<1|1,mid+1,r,u,v,val);
st[node]=max(st[node<<1],st[node<<1|1]);
st[node].first+=lazy[node];
}
pair <int, int> get(int node, int l, int r, int u, int v){
if (l>v||r<u||l>r||u>v)
return {0,0};
if (l>=u&&r<=v)
return st[node];
int mid=(l+r)>>1;
return max(get(node<<1,l,mid,u,v),get(node<<1|1,mid+1,r,u,v));
}
void jump(int &u, int val){
auto [mx,v]=get(1,1,n,tin[u],tout[u]);
res=(res+(h[u]-h[nxt[v]])*val%mod)%mod;
u=nxt[v];
}
void walk(int u, int val){
auto [cur,V]=get(1,1,n,tin[u],tout[u]);
jump(u,val);
cur+=val;
while (u){
int w=p[u];
auto [mx,v]=get(1,1,n,tin[w],tout[w]);
int pos=lower_bound(ke2[w].begin(),ke2[w].end(),make_pair(tout[v],0LL))-ke2[w].begin();
int c=ke2[w][pos].second;
auto [mx2,v2]=max(get(1,1,n,tin[w],tin[c]-1),get(1,1,n,tout[c]+1,tout[w]));
if (make_pair(cur,V)>make_pair(mx,v)){
nxt[V]=nxt[v];
nxt[v]=c;
jump(u,cur-mx);
res=(res+mx-mx2)%mod;
}
else{
res=(res+max(cur-mx2,0LL))%mod;
break;
}
}
}
int32_t main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n;
for (int i=1;i<n;i++){
cin >> p[i];
ke[p[i]].push_back(i);
}
for (int i=1;i<n;i++)
cin >> d[i];
dfs(0);
build(1,1,n);
cout << res << '\n';
cin >> q;
int v,add;
while (q--){
cin >> v >> add;
walk(v,add);
update(1,1,n,tin[v],tout[v],add);
cout << res << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5027 ms |
12888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5061 ms |
27456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5057 ms |
30080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5027 ms |
12888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
