#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
//~ struct ST{
//~ int tree[N << 2], mn[N << 2], mx[N << 2];
//~ bool is[N << 2], val[N << 2];
//~ void push(int x, int lx, int rx){
//~ if(lx == rx || !is[x]) return;
//~ int m = (lx + rx) >> 1;
//~ tree[x<<1] = mn[x] % mod * 1ll * (m - lx + 1) % mod;
//~ tree[x<<1|1] = mn[x] % mod * 1ll * (rx - m) % mod;
//~ mn[x<<1] = mn[x<<1|1] = mn[x];
//~ mx[x<<1] = mx[x<<1|1] = mx[x];
//~ is[x<<1] = is[x<<1|1] = 1;
//~ is[x] = 0;
//~ }
//~ void umax(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
//~ if(lx > r || rx < l || mn[x] >= v) return;
//~ if(lx >= l && rx <= r && mx[x] <= v){
//~ tree[x] = (rx - lx + 1) * 1ll * (v % mod) % mod;
//~ mn[x] = mx[x] = v; is[x] = 1;
//~ return;
//~ } push(x, lx, rx);
//~ int m = (lx + rx) >> 1;
//~ umax(l, r, v, lx, m, x<<1);
//~ umax(l, r, v, m+1, rx, x<<1|1);
//~ tree[x] = tree[x<<1] + tree[x<<1|1];
//~ mn[x] = min(mn[x<<1], mn[x<<1|1]);
//~ mx[x] = max(mx[x<<1], mx[x<<1|1]);
//~ }
//~ int get(int i, int lx = 0, int rx = N, int x = 1){
//~ if(lx == rx) return mx[x];
//~ push(x, lx, rx);
//~ int m = (lx + rx) >> 1;
//~ if(i <= m) return get(i, lx, m, x<<1);
//~ else return get(i, m+1, rx, x<<1|1);
//~ }
//~ }tree;
vector<int> edges[N];
int dp[N][2], in[N][2];
int c[N], pp[N];
//~ int hv[N], pos[N], par[N], t;
void dfs(int u){
in[u][0] = in[u][1] = u;
dp[u][0] = dp[u][1] = 0;
for(auto x : edges[u]){
dfs(x);
if(dp[x][0] + c[x] > dp[u][1]){
dp[u][1] = dp[x][0] + c[x];
in[u][1] = x;
}
if(dp[u][1] > dp[u][0]){
swap(dp[u][0], dp[u][1]);
swap(in[u][0], in[u][1]);
}
}
}
//~ void dec(int u){
//~ pos[u] = t++;
//~ tree.umax(pos[u], pos[u], dp[u]);
//~ if(~hv[u]){
//~ par[hv[u]] = par[u];
//~ dec(hv[u]);
//~ }
//~ for(auto x : edges[u]){
//~ if(x[0] == hv[u]) continue;
//~ par[x[0]] = x[0];
//~ dec(x[0]);
//~ }
//~ }
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
memset(pp, -1, sizeof pp);
for(int i=1;i<n;i++) cin>>pp[i];
for(int i=1;i<n;i++){
cin>>c[i];
edges[pp[i]].push_back(i);
}
dfs(0);
//~ dec(0);
int res = 0;
for(int i=0;i<n;i++){
res += dp[i][0] + dp[i][1];
}
cout<<res % mod<<"\n";
int q; cin>>q;
while(q--){
int i, v; cin>>i>>v;
//~ for(int i=0;i<n;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<"\n";
c[i] += v;
while(i){
int p = pp[i];
if(in[p][0] == i){
res = (res - dp[p][0] + dp[i][0] + c[i]);
dp[p][0] = dp[i][0] + c[i];
} else {
if(dp[p][0] < dp[i][0] + c[i]){
res = (res - dp[p][1] + dp[i][0] + c[i]);
dp[p][1] = dp[p][0], in[p][1] = in[p][0];
dp[p][0] = dp[i][0] + c[i], in[p][0] = i;
} else {
if(dp[p][1] < dp[i][0] + c[i]){
res = (res - dp[p][1] + dp[i][0] + c[i]);
dp[p][1] = dp[i][0] + c[i], in[p][1] = i;
}
break;
}
}
i = p;
}
cout<<res % mod<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3524 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
12216 KB |
Output is correct |
| 2 |
Correct |
63 ms |
10868 KB |
Output is correct |
| 3 |
Correct |
45 ms |
11236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
656 ms |
14184 KB |
Output is correct |
| 2 |
Execution timed out |
5006 ms |
16868 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3524 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 4 |
Correct |
66 ms |
12216 KB |
Output is correct |
| 5 |
Correct |
63 ms |
10868 KB |
Output is correct |
| 6 |
Correct |
45 ms |
11236 KB |
Output is correct |
| 7 |
Correct |
656 ms |
14184 KB |
Output is correct |
| 8 |
Execution timed out |
5006 ms |
16868 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
