#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod = 1e9 + 7;
struct aint
{
int ai[500005],lazy[500005];
void propag(int nod, int a, int b)
{
if(lazy[nod]==0)
{
return;
}
int mij = (a + b) >> 1;
ai[nod*2] += lazy[nod] * (mij - a + 1);
ai[nod*2+1] += lazy[nod] * (b - mij);
lazy[nod*2] += lazy[nod];
lazy[nod*2+1] += lazy[nod];
lazy[nod] = 0;
}
void update(int ua, int ub, int val, int nod, int a, int b)
{
if(ua<=a && ub>=b)
{
ai[nod] += val * (b - a + 1);
lazy[nod] += val;
return;
}
propag(nod,a,b);
int mij = (a + b) >> 1;
if(ua<=mij)
{
update(ua,ub,val,nod*2,a,mij);
}
if(ub>mij)
{
update(ua,ub,val,nod*2+1,mij+1,b);
}
ai[nod] = ai[nod*2] + ai[nod*2+1];
}
int query(int poz, int nod, int a, int b)
{
if(a==b)
{
return ai[nod];
}
propag(nod,a,b);
int mij = (a + b) >> 1;
if(poz<=mij)
{
return query(poz,nod*2,a,mij);
}
return query(poz,nod*2+1,mij+1,b);
}
};
aint ai,ai2;
int n,q;
int w[100005],Mx[100005];
int l[100005],t[100005],c[100005],poz[100005],lvl[100005];
int cnt = 0, paths = 1;
int d[100005];
pair<int,int> Max[100005],Max2[100005];
vector<int> G[100005];
set<pair<int,int>,greater<pair<int,int>>>s[100005];
vector<int> se;
void get_w(int nod, int dad = 0)
{
w[nod] = 1;
for(auto it : G[nod])
{
if(it==dad)
{
continue;
}
get_w(it,nod);
w[nod] += w[it];
if(w[it] > w[Mx[nod]])
{
Mx[nod] = it;
}
}
}
void get_paths(int nod, int dad = 0, int level = 1)
{
poz[nod] = (++cnt);
l[nod] = paths;
lvl[nod] = level;
t[nod] = dad;
if(G[nod].size()==1 && nod!=1)
{
return;
}
get_paths(Mx[nod],nod,level+1);
for(auto it : G[nod])
{
if(it==dad || it==Mx[nod])
{
continue;
}
++paths;
c[paths] = it;
get_paths(it,nod,level+1);
}
}
void dfs(int nod, int dad = 0)
{
for(auto it : G[nod])
{
if(it==dad)
{
continue;
}
dfs(it,nod);
if(Max[it].first + d[it] > Max[nod].first)
{
Max2[nod] = Max[nod];
Max[nod].first = Max[it].first + d[it];
Max[nod].second = it;
}
else if(Max[it].first + d[it] > Max2[nod].first)
{
Max2[nod].first = Max[it].first + d[it];
Max2[nod].second = it;
}
}
for(auto it : G[nod])
{
if(it==dad || it==Max[nod].second)
{
continue;
}
se.push_back(it);
}
}
void add_se(int nod)
{
s[l[nod]].insert({lvl[nod],nod});
}
void remove_se(int nod)
{
auto it = s[l[nod]].lower_bound({lvl[nod],nod});
s[l[nod]].erase(it);
}
int find_next_se(int nod)
{
while(nod)
{
auto it = s[l[nod]].lower_bound({lvl[nod],nod});
if(it!=s[l[nod]].end())
{
return it->second;
}
nod = t[c[l[nod]]];
}
return 1;
}
void update_arb(int x, int y, int val)
{
if(lvl[x] > lvl[y])
{
return;
}
while(l[x]!=l[y])
{
ai.update(poz[c[l[y]]],poz[y],+val,1,1,n);
y = t[c[l[y]]];
}
ai.update(poz[x],poz[y],+val,1,1,n);
}
void update(int nod, int val)
{
while(nod!=1)
{
int anc = find_next_se(nod);
update_arb(anc,t[nod],+val);
nod = anc;
if(nod==1)
{
break;
}
int cnd = ai.query(poz[nod],1,1,n) + d[nod];
int dad = t[nod];
int Maxdad = ai.query(poz[dad],1,1,n);
int Max2dad = ai2.query(poz[dad],1,1,n);
if(cnd <= Max2dad)
{
break;
}
if(cnd > Maxdad)
{
remove_se(nod);
add_se(Max[dad].second);
ai2.update(poz[dad],poz[dad],Maxdad-Max2dad,1,1,n);
Max2[dad].second = Max[dad].second;
ai.update(poz[dad],poz[dad],cnd-Maxdad,1,1,n);
Max[dad].second = nod;
val = cnd - Maxdad;
nod = dad;
}
else if(cnd > Max2dad)
{
Max2[dad].second = nod;
ai2.update(poz[dad],poz[dad],cnd-Max2dad,1,1,n);
break;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("nr.in","r",stdin);
// freopen("nr.out","w",stdout);
cin>>n;
for(int i=2;i<=n;i++)
{
int t;
cin>>t;
++t;
G[i].push_back(t);
G[t].push_back(i);
}
for(int i=2;i<=n;i++)
{
cin>>d[i];
}
dfs(1);
get_w(1);
c[1] = 1;
get_paths(1);
for(auto it : se)
{
add_se(it);
}
for(int i=1;i<=n;i++)
{
ai.update(poz[i],poz[i],Max[i].first,1,1,n);
ai2.update(poz[i],poz[i],Max2[i].first,1,1,n);
}
cout<<(ai.ai[1] + ai2.ai[1]) % Mod<<'\n';
cin>>q;
for(int i=1;i<=q;i++)
{
int nod,val;
cin>>nod>>val;
++nod;
d[nod] += val;
update(nod,val);
cout<<(ai.ai[1] + ai2.ai[1]) % Mod<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
275 ms |
32204 KB |
Output is correct |
| 2 |
Correct |
119 ms |
33600 KB |
Output is correct |
| 3 |
Correct |
135 ms |
33832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
32724 KB |
Output is correct |
| 2 |
Correct |
137 ms |
36988 KB |
Output is correct |
| 3 |
Correct |
186 ms |
35224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7624 KB |
Output is correct |
| 4 |
Correct |
275 ms |
32204 KB |
Output is correct |
| 5 |
Correct |
119 ms |
33600 KB |
Output is correct |
| 6 |
Correct |
135 ms |
33832 KB |
Output is correct |
| 7 |
Correct |
177 ms |
32724 KB |
Output is correct |
| 8 |
Correct |
137 ms |
36988 KB |
Output is correct |
| 9 |
Correct |
186 ms |
35224 KB |
Output is correct |
| 10 |
Correct |
180 ms |
34792 KB |
Output is correct |
| 11 |
Correct |
139 ms |
36676 KB |
Output is correct |
| 12 |
Correct |
172 ms |
34956 KB |
Output is correct |
| 13 |
Correct |
113 ms |
32632 KB |
Output is correct |
| 14 |
Correct |
109 ms |
33612 KB |
Output is correct |
