#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]=mx[u][1]={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 recompute(int node, int val){
st[node].first+=val;
lazy[node]+=val;
}
void down(int node, int l, int r){
if (!lazy[node]||l==r)
return;
recompute(node<<1,lazy[node]);
recompute(node<<1|1,lazy[node]);
lazy[node]=0;
}
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){
recompute(node,val);
return;
}
down(node,l,r);
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]);
}
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];
down(node,l,r);
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 v, int val){
res=(res+(h[u]-h[v])*val%mod)%mod;
u=nxt[v];
}
void walk(int u, int val){
int tmp=u;
auto [cur,V]=get(1,1,n,tin[u],tout[u]);
jump(u,nxt[V],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,nxt[V],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';
}
}
Compilation message
arboras.cpp: In function 'void walk(long long int, long long int)':
arboras.cpp:78:9: warning: unused variable 'tmp' [-Wunused-variable]
78 | int tmp=u;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
4 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
28260 KB |
Output is correct |
2 |
Correct |
133 ms |
27240 KB |
Output is correct |
3 |
Correct |
147 ms |
27984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
31056 KB |
Output is correct |
2 |
Correct |
117 ms |
35840 KB |
Output is correct |
3 |
Correct |
180 ms |
30032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
4 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
214 ms |
28260 KB |
Output is correct |
5 |
Correct |
133 ms |
27240 KB |
Output is correct |
6 |
Correct |
147 ms |
27984 KB |
Output is correct |
7 |
Correct |
167 ms |
31056 KB |
Output is correct |
8 |
Correct |
117 ms |
35840 KB |
Output is correct |
9 |
Correct |
180 ms |
30032 KB |
Output is correct |
10 |
Correct |
178 ms |
32080 KB |
Output is correct |
11 |
Correct |
107 ms |
36688 KB |
Output is correct |
12 |
Correct |
167 ms |
30308 KB |
Output is correct |
13 |
Correct |
107 ms |
34896 KB |
Output is correct |
14 |
Correct |
100 ms |
37972 KB |
Output is correct |