Submission #1297576

#TimeUsernameProblemLanguageResultExecution timeMemory
1297576MisterReaperArboras (RMI20_arboras)C++20
24 / 100
5092 ms11008 KiB
// File C.cpp created on 01.12.2025 at 09:17:42
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int md = int(1E9) + 7;

int add(int x, int y) {
    x += y;
    if (x >= md) {
        x -= md;
    }
    return x;
}
int sub(int x, int y) {
    x -= y;
    if (x < 0) {
        x += md;
    }
    return x;
}

int N;
std::vector<int> P;
std::vector<i64> D;
std::vector<std::vector<int>> adj;
std::vector<std::array<std::pair<i64, int>, 2>> mx;

void upd(std::array<std::pair<i64, int>, 2>& x, std::pair<i64, int> y) {
    if (x[0].second == y.second) {
        x[0] = y;
    } else if (x[1].second == y.second) {
        x[1] = y;
        if (x[1].first > x[0].first) {
            std::swap(x[0], x[1]);
        }
    } else {
        if (y.first > x[0].first) {
            x[1] = x[0];
            x[0] = y;
        } else if (y.first > x[1].first) {
            x[1] = y;
        }
    }
}

int f(std::array<std::pair<i64, int>, 2> x) {
    return (x[0].first + x[1].first) % md;
}

void dfs(int v) {
    for (auto u : adj[v]) {
        dfs(u);
        upd(mx[v], {mx[u][0].first + D[u], u});
    }
}

int ans = 0;

void init() {
    dfs(0);
    for (int v = 0; v < N; ++v) {
        ans = add(ans, f(mx[v]));
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N;

    P.resize(N);
    D.resize(N);
    adj.resize(N);
    mx.resize(N);

    for (int i = 1; i < N; ++i) {
        std::cin >> P[i];
        adj[P[i]].emplace_back(i);
    }
    for (int i = 1; i < N; ++i) {
        std::cin >> D[i];
    }

    init();

    std::cout << ans << '\n';

    int Q;
    std::cin >> Q;

    while (Q--) {
        int v, x;
        std::cin >> v >> x;
        D[v] += x;
        while (v != 0) {
            int u = P[v];
            ans = sub(ans, f(mx[u]));
            upd(mx[u], {mx[v][0].first + D[v], v});
            ans = add(ans, f(mx[u]));
            v = u;
        }
        std::cout << ans << '\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...