제출 #422869

#제출 시각아이디문제언어결과실행 시간메모리
422869valerikkArboras (RMI20_arboras)C++17
24 / 100
509 ms12152 KiB
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 1e5 + 7;
const int md = 1e9 + 7;

int n, q;
int p[N], d[N];
vector<int> g[N];
int best[N], best2[N];
int dp[N], dp2[N];
int sum = 0;

void dfs(int v) {
    best[v] = best2[v] = -1;
    dp[v] = dp2[v] = 0;
    for (int u : g[v]) {
        dfs(u);
        if (dp[u] + d[u] > dp[v]) {
            dp2[v] = dp[v], best2[v] = best[v];
            dp[v] = dp[u] + d[u], best[v] = u;
        } else if (dp[u] + d[u] > dp2[v]) {
            dp2[v] = dp[u] + d[u];
            best2[v] = u;
        }
    }
    sum += dp[v] + dp2[v];
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    p[0] = -1;
    for (int i = 1; i < n; ++i) {
        cin >> p[i];
        g[p[i]].push_back(i);
    }
    for (int i = 1; i < n; ++i) {
        cin >> d[i];
    }
    dfs(0);
    cout << sum << "\n";
    cin >> q;
    while (q--) {
        int v, add;
        cin >> v >> add;
        d[v] += add;
        while (v != 0) {
            if (v == best[p[v]]) {
                sum += dp[v] + d[v] - dp[p[v]];
                dp[p[v]] = dp[v] + d[v];
            } else if (dp[v] + d[v] > dp[p[v]]) {
                sum += dp[p[v]] - dp2[p[v]] + dp[v] + d[v] - dp[p[v]];
                dp2[p[v]] = dp[p[v]], best[p[v]] = best2[p[v]];
                dp[p[v]] = dp[v] + d[v], best[p[v]] = v;
            } else {
                if (dp[v] + d[v] > dp2[p[v]]) {
                    sum += dp[v] + d[v] - dp2[p[v]];
                    dp2[p[v]] = dp[v] + d[v], best2[p[v]] = v;
                }
                break;
            }
            v = p[v];
        }
        cout << sum % md << "\n";
    }
    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...