/**
* user: dossi-74c
* fname: Tommaso
* lname: Dossi
* task: Arboras
* score: 13.0
* date: 2020-12-04 11:54:27.709767
*/
#include<bits/stdc++.h>
#pragma gcc optimize("O3")
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN = 100010;
const ll MOD = 1000000007;
vi adj[MAXN];
ll p[MAXN],w[MAXN];
ll m1[MAXN],m2[MAXN];
ll pr1[MAXN],pr2[MAXN];
ll cnt[MAXN];
int Q,N,a,b;
void dfs(int pp){
for(auto a: adj[pp]){
dfs(a);
if(m1[a]+w[a]>m2[pp]){
m2[pp] = m1[a]+w[a];
pr2[pp] = a;
}
if(m2[pp]>m1[pp]){
swap(m1[pp],m2[pp]);
swap(pr1[pp],pr2[pp]);
}
}
cnt[pr2[pp]] = 1;
cnt[pr1[pp]] = cnt[pp]+1;
}
ll ans;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(NULL);
cin >> N;
for(int i = 1; i < N; i++){
cin >> p[i];
adj[p[i]].pb(i);
}
for(int i = 1; i < N; i++){
cin >> w[i];
}
dfs(0);
for(int i = 0; i < N; i++){
ans+=m1[i]+m2[i]; ans%=MOD;
}
cout << ans << "\n";
cin >> Q;
int k,pp;
while(Q--){
cin >> a >> b;
w[a]+=b;
k = 0;
while(a!=0){
if(k > 50)break;
k++;
pp = p[a];
if(m1[a]+w[a]>m1[pp]){
if(pr1[pp]!=a){
ans+=w[a]+m1[a] - m2[pp];
ans%MOD;
m2[pp] = m1[pp];
pr2[pp] = pr1[pp];
}else{
ans+=w[a]+m1[a]-m1[pp];
ans%=MOD;
}
m1[pp] = w[a] + m1[a];
pr1[pp] = a;
}else if(m1[a] + w[a] > m2[pp] && pr1[pp]!= a){
ans += m1[a] + w[a] - m2[pp];
ans%MOD;
m2[pp] = m1[a] + w[a];
pr2[pp] = a;
}else break;
a = pp;
}
if(k > 50)ans+=cnt[a];
ans%=MOD;
cout << ans << "\n";
}
/*while(Q--){
cin >> a >> b;
if(a == 0){
cout << ans <<"\n";
continue;
}
ans += cnt[a];
ans%=MOD;
cout << ans <<"\n";
}*/
return 0;
}
Compilation message
arboras.cpp:10: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
10 | #pragma gcc optimize("O3")
|
arboras.cpp: In function 'int main()':
arboras.cpp:74:9: warning: statement has no effect [-Wunused-value]
74 | ans%MOD;
| ~~~^~~~
arboras.cpp:86:8: warning: statement has no effect [-Wunused-value]
86 | ans%MOD;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
10664 KB |
Output is correct |
| 2 |
Correct |
69 ms |
5520 KB |
Output is correct |
| 3 |
Correct |
55 ms |
5956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
12540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
