/**
* user: perju-verzotti-712
* fname: Luca
* lname: Perju-Verzotti
* task: Arboras
* score: 100.0
* date: 2020-12-04 11:29:29.204456
*/
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long p[100003],t[100003],sz[100003],depth[100003],heavyhead[100003],heavychild[100003];
vector<long long>v[100003];
long long d[100003];
unsigned long long dp[100003],dp1[100003];
long long bstfiu[100003];
long long pzlin[100003];
long long cnttidk;
long long lsb (long long x)
{
return x&-x;
}
long long aib[100003];
void update (long long pz, long long val)
{
for(long long i=pz;i<=100000;i+=lsb(i))
aib[i]=aib[i]+val;
}
long long query (long long pz)
{
long long rz=0;
for(long long i=pz;i>0;i-=lsb(i))
rz=rz+aib[i];
return rz;
}
long long s=0;
long long tata (long long pz)
{
if(t[pz]==0 || t[pz]==pz)
return pz;
if(cnttidk>10)
return tata(t[pz]);
else
return t[pz]=tata(t[pz]);
}
void dfsinit (long long pz)
{
t[pz]=pz;
sz[pz]=1;
if(v[pz].size()==0)
return;
long long bst=v[pz][0];
long long b1=-1,b2=-1;
for(long long i=0;i<v[pz].size();++i)
{
depth[v[pz][i]]=1+depth[pz];
dfsinit(v[pz][i]);
sz[pz]+=sz[v[pz][i]];
if(sz[v[pz][i]]>sz[bst])
bst=v[pz][i];
unsigned long long dpc=dp[v[pz][i]]+d[v[pz][i]];
if(b1==-1 || dpc>dp[b1]+d[b1])
{
b2=b1;
b1=v[pz][i];
}
else if(b2==-1 || dpc>dp[b2]+d[b2])
b2=v[pz][i];
}
dp[pz]=dp[b1]+d[b1];
if(b2!=-1)
dp1[pz]=dp[b2]+d[b2];
t[b1]=pz;
bstfiu[pz]=b1;
s=(s+dp[pz])%mod;
s=(s+dp1[pz])%mod;
heavychild[pz]=bst;
}
void dfsinit1 (long long pz)
{
if(heavychild[p[pz]]==pz)
heavyhead[pz]=heavyhead[p[pz]];
else
{
heavyhead[pz]=pz;
++cnttidk;
}
for(long long i=0;i<v[pz].size();++i)
dfsinit1(v[pz][i]);
}
long long tmpc=0;
void dfsinit2 (long long pz)
{
pzlin[pz]=++tmpc;
if(heavychild[pz])
dfsinit2(heavychild[pz]);
for(long long i=0;i<v[pz].size();++i)
{
if(v[pz][i]==heavychild[pz])
continue;
dfsinit2(v[pz][i]);
}
}
void updatelin (long long a, long long b, long long val)
{
if(depth[a]>depth[b])
return;
s=(s+val%mod*1LL*(depth[b]-depth[a]+1)%mod)%mod;
while(heavyhead[b]!=heavyhead[a])
{
update(pzlin[heavyhead[b]],val);
update(pzlin[b]+1,-val);
b=p[heavyhead[b]];
}
if(heavyhead[a]==heavyhead[b])
{
update(pzlin[a],val);
update(pzlin[b]+1,-val);
return;
}
}
void jegupdate (long long pz, long long val)
{
d[pz]+=val;
long long pzc=pz;
while(1)
{
long long tc=tata(pzc);
long long ptc=p[tc];
if(p[pzc])
updatelin(tc,p[pzc],val);
if(tc==1)
break;
pzc=tc;
long long dpc=query(pzlin[pzc]);
long long dpt=query(pzlin[ptc]);
if(dpc+d[pzc]>dpt)
{
t[bstfiu[ptc]]=bstfiu[ptc];
bstfiu[ptc]=pzc;
t[pzc]=ptc;
val=dpc+d[pzc]-dpt;
s=(s+dpt-dp1[ptc])%mod;
dp1[ptc]=dpt;
// update(pzlin[ptc],val);
// s=(s+val)%mod;
}
else
{
if(dpc+d[pzc]>dp1[ptc])
{
s=(s+dpc+d[pzc]-dp1[ptc])%mod;
dp1[ptc]=dpc+d[pzc];
}
break;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
long long n,i,j;
cin>>n;
for(i=2;i<=n;++i)
{
cin>>p[i];
++p[i];
v[p[i]].push_back(i);
}
for(i=2;i<=n;++i)
cin>>d[i];
depth[1]=1;
dfsinit(1);
dfsinit1(1);
dfsinit2(1);
/*if(cnttidk<=10)
{
i/=0;
++p[-100];
return 0;
}*/
for(i=1;i<=n;++i)
{
update(pzlin[i],dp[i]);
update(pzlin[i]+1,-dp[i]);
}
long long q;
cin>>q;
cout<<s<<'\n';
for(i=1;i<=q;++i)
{
long long a,b;
cin>>a>>b;
++a;
jegupdate(a,b);
cout<<s<<'\n';
}
return 0;
}
Compilation message
arboras.cpp: In function 'void dfsinit(long long int)':
arboras.cpp:55:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(long long i=0;i<v[pz].size();++i)
| ~^~~~~~~~~~~~~
arboras.cpp: In function 'void dfsinit1(long long int)':
arboras.cpp:89:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(long long i=0;i<v[pz].size();++i)
| ~^~~~~~~~~~~~~
arboras.cpp: In function 'void dfsinit2(long long int)':
arboras.cpp:98:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(long long i=0;i<v[pz].size();++i)
| ~^~~~~~~~~~~~~
arboras.cpp: In function 'void jegupdate(long long int, long long int)':
arboras.cpp:151:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
151 | if(dpc+d[pzc]>dp1[ptc])
| ~~~~~~~~~~^~~~~~~~~
arboras.cpp: In function 'int main()':
arboras.cpp:163:19: warning: unused variable 'j' [-Wunused-variable]
163 | long long n,i,j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
14780 KB |
Output is correct |
| 2 |
Correct |
253 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
244 ms |
11048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
560 ms |
16624 KB |
Output is correct |
| 2 |
Correct |
3933 ms |
17084 KB |
Output is correct |
| 3 |
Correct |
329 ms |
12308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2844 KB |
Output is correct |
| 4 |
Correct |
316 ms |
14780 KB |
Output is correct |
| 5 |
Correct |
253 ms |
10584 KB |
Output is correct |
| 6 |
Correct |
244 ms |
11048 KB |
Output is correct |
| 7 |
Correct |
560 ms |
16624 KB |
Output is correct |
| 8 |
Correct |
3933 ms |
17084 KB |
Output is correct |
| 9 |
Correct |
329 ms |
12308 KB |
Output is correct |
| 10 |
Correct |
727 ms |
16580 KB |
Output is correct |
| 11 |
Correct |
4265 ms |
17004 KB |
Output is correct |
| 12 |
Correct |
385 ms |
12440 KB |
Output is correct |
| 13 |
Correct |
233 ms |
18440 KB |
Output is correct |
| 14 |
Correct |
238 ms |
19200 KB |
Output is correct |
