# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, mod = 1e9 + 7;
//int n,sz[N],mx,bigchild[N],in[N],out[N],p_[N],chain[N],tin,dep[N],to_par[N],x[N];
//vector <pii> v[N];
int n,dep[N],to_par[N],ans,p_[N],is[N];
pii mx[N][2], pot[2];
vector <pii> v[N];
void dfs(int a, int p) {
dep[a] = dep[p] + to_par[a];
vector <pii> vec;
for (pii sth : v[a]) {
int to = sth.f, c = sth.s;
if (to == p) continue;
dfs(to, a);
vec.pb({dep[to], to});
}
sort(vec.rbegin(), vec.rend());
if (vec.size() > 0) mx[a][0] = vec[0];
if (vec.size() > 1) mx[a][1] = vec[1];
ans += mx[a][0].f + mx[a][1].f;
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for (int i = 2; i <= n; i++) {
cin>>p_[i]; p_[i]++;
}
for (int i = 2; i <= n; i++) {
int c;
cin>>c;
to_par[i] = c;
v[p_[i]].pb({i, c});
v[i].pb({p_[i], c});
}
for (int i = 1; i <= n ;i++) {
mx[i][0] = {0, i};
mx[i][1] = {0, 0};
}
dfs(1, 0);
cout<<ans<<"\n";
int q; cin>>q;
while (q--) {
int vert, to_add;
cin>>vert>>to_add; vert++;
int cur = vert;
// pot[1] = mx[vert][1]; pot[1].f += to_add;
int best = mx[cur][0].f + to_add;
while (cur != 1) {
is[p_[cur]] = mx[cur][0].f + to_par[cur];
cur = p_[cur];
}
cur = vert;
while (cur != 1) {
pot[0].f = is[p_[cur]]; pot[0].s = cur;
best += to_par[cur];
pot[0].f = max(pot[0].f, best);
ans -= (mx[p_[cur]][0].f + mx[p_[cur]][1].f) % mod;
ans += mod;
ans %= mod;
for (int j = 0; j <= 0; j++) {
if (pot[j].s != 0) {
if (mx[p_[cur]][0].f <= pot[j].f) {
if (cur == mx[p_[cur]][0].s) mx[p_[cur]][0] = pot[j];
else mx[p_[cur]][1] = mx[p_[cur]][0], mx[p_[cur]][0] = pot[j];
continue;
}
if (mx[p_[cur]][1].f <= pot[j].f) {
if (cur == mx[p_[cur]][0].s) continue;
mx[p_[cur]][1] = pot[j];
}
}
}
// cout<<cur<<" --- > "<<mx[cur][0].f<<" "<<mx[cur][0].s<<" "<<mx[cur][1].f<<" "<<mx[cur][1].s<<"\n";
ans += (mx[p_[cur]][0].f + mx[p_[cur]][1].f) % mod;
ans %= mod;
cur = p_[cur];
}
to_par[vert] += to_add;
cout<<ans<<"\n";
}
}
Compilation message
arboras.cpp: In function 'void dfs(long long int, long long int)':
arboras.cpp:18:19: warning: unused variable 'c' [-Wunused-variable]
18 | int to = sth.f, c = sth.s;
| ^
arboras.cpp: At global scope:
arboras.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
28 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
21736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5035 ms |
24084 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
