Submission #1297552

#TimeUsernameProblemLanguageResultExecution timeMemory
1297552ThunnusArboras (RMI20_arboras)C++20
24 / 100
5091 ms24740 KiB
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,O3")
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define se second
#define fi first
#define pii pair<int, int>
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;

inline void solve(){
    int n, q;
    cin >> n;
    vi par(n), d(n);
    vector<vector<pii>> adj(n);
    vector<multiset<int, greater<int>>> best(n);
    for(int i = 1; i < n; i++){
        cin >> par[i];
    }
    for(int i = 1; i < n; i++){
        cin >> d[i];
        adj[par[i]].emplace_back(i, d[i]);
    }

    vi dep(n);
    vvi dp(n, vi(2));
    int maxd = 0, ans = 0;
    function<void(int)> dfs = [&](int v) -> void {
        maxd = max(maxd, dep[v]);
        for(pii &u : adj[v]){
            dep[u.fi] = dep[v] + 1;
            dfs(u.fi);
            int val = dp[u.fi][1] + u.se;
            best[v].emplace(val);
            if(val > dp[v][1]){
                dp[v][0] = dp[v][1];
                dp[v][1] = val;
            }
            else if(val > dp[v][0]){
                dp[v][0] = val;
            }
        }
        ans = (ans + (dp[v][0] + dp[v][1])) % MOD;
        return;
    };
    dfs(0);
    
    cout << ans << "\n";
    cin >> q;
    while(q--){
        int v, add;
        cin >> v >> add;
        best[par[v]].erase(best[par[v]].find(dp[v][1] + d[v]));
        d[v] += add;
        best[par[v]].emplace(dp[v][1] + d[v]);
        while(v){
            ans = (ans - (dp[par[v]][0] + dp[par[v]][1]) + MOD) % MOD;
            if(par[v]){
                best[par[par[v]]].erase(best[par[par[v]]].find(dp[par[v]][1] + d[par[v]]));
            }
            int c1 = dp[par[v]][1];
            dp[par[v]][1] = *best[par[v]].begin();
            best[par[v]].erase(best[par[v]].begin());
            dp[par[v]][0] = *best[par[v]].begin();
            best[par[v]].emplace(dp[par[v]][1]);
            ans = (ans + (dp[par[v]][0] + dp[par[v]][1])) % MOD;
            if(par[v]){
                best[par[par[v]]].emplace(dp[par[v]][1] + d[par[v]]);
            }
            if(c1 == dp[par[v]][1]) break;
            v = par[v];
        }
        cout << ans << "\n";
        /*cout << "dp: ";
        for(int v = 0; v < n; v++){
			cout << "v: " << v << " " << dp[v][0] << " " << dp[v][1] << "    ";
		}
		cout << "\n";*/
    }
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...