Submission #1297623

#TimeUsernameProblemLanguageResultExecution timeMemory
1297623dostsArboras (RMI20_arboras)C++20
0 / 100
5085 ms25000 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;

const int N = 1e5+1;
vi edges[N],par(N,0),baba(N,0),cid(N),hei(N),latest(N);
multiset<int> h[N];
int timer = 1;

int add(int x,int y) {
    return ((x%MOD)+(y%MOD))%MOD;
}

int mult(int x,int y) {
    return ((x%MOD)*(y%MOD))%MOD;
}

int n;

int dfs(int node) {
    hei[node] = 0;
    for (auto it : edges[node]) {
        dfs(it);
        h[node].insert(hei[it]+baba[it]);
        latest[it] = hei[it]+baba[it];
        hei[node] = max(hei[node],hei[it]+baba[it]);
    }
    return hei[node];
}

void solve() {
    cin >> n;
    for (int i = 2;i<=n;i++) {
        cin >> par[i];
        par[i]++;
        edges[par[i]].push_back(i);
    }
    for (int i = 2;i<=n;i++) cin >> baba[i];
    int ans = 0;
    auto gettwo = [&](int node) -> int {
        if (big(h[node]) == 1) return 0;
        return add(*h[node].rbegin(),*prev(h[node].rbegin()));
    };

    auto upd = [&](int node,int ad) -> void {
        int cur = node;
        baba[node]+=ad;
        while (cur>1) { 
            hei[cur] = *h[cur].rbegin();
            ans=add(ans,MOD-gettwo(par[cur]));
            h[par[cur]].erase(h[par[cur]].find(latest[cur]));
            h[par[cur]].insert(hei[cur]+baba[cur]);
            latest[cur] = hei[cur]+baba[cur];
            ans=add(ans,gettwo(par[cur]));
            cur = par[cur]; 
        }

    };

    auto init = [&]() -> void {
        for (int i=1;i<=n;i++) h[i].insert(0);
        dfs(1);
        for (int i=1;i<=n;i++) ans=add(ans,gettwo(i));
    };
    init();
    cout << ans << '\n';
    int q;
    cin >> q;
    while (q--) {
        int v,ad;
        cin >> v >> ad;
        v++;
        upd(v,ad);
        cout << ans << '\n';
    }

} 

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