Submission #597425

#	Time	Username	Problem	Language	Result	Execution time	Memory
597425		definitelynotmee	Arboras (RMI20_arboras)	C++98	0 / 100	3355 ms	10788 KiB

arboras

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;
const int MOD = 1e9+7;

int main(){
    
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n;

    vector<ll> edge(n);
    vector<int> pai(n);
    matrix<int> g(n);

    for(int i = 1; i < n; i++)
        cin >> pai[i], g[pai[i]].push_back(i);
    for(int i = 1; i < n; i++)
        cin >> edge[i];
    
    vector<pair<pll,pll>> resp(n);

    auto dfs =[&](int id, auto dfs)->void{
        for(int i : g[id]){
            dfs(i,dfs);
            pll carry = {resp[i].ff.ff+edge[i],i};
            if(carry > resp[i].ss){
                if(carry >= resp[i].ff){
                    swap(resp[i].ff,resp[i].ss);
                    resp[i].ff = carry;
                } else resp[i].ss = carry;
            }
        }
    };
    
    dfs(0,dfs);

    ll ans = 0;

    for(pair<pll,pll> i : resp){
        ans+=i.ff.ff+i.ss.ff;
        ans%=MOD;
    }

    cout << ans << '\n';
    
    cin >> q;

    while(q--){
        ll id, x;
        cin >> id >> x;
        edge[id]+= x;
        while(id && edge[id] + resp[id].ff.ff > resp[pai[id]].ss.ff){
            ans-=resp[pai[id]].ff.ff+resp[pai[id]].ss.ff;

            if(resp[pai[id]].ff.ss == id){
                resp[pai[id]].ff.ff = resp[id].ff.ff+edge[id];
            } else if(resp[pai[id]].ss.ss == id){
                resp[pai[id]].ss.ff = resp[id].ff.ff+edge[id];
            } else { 
                pll carry = {resp[id].ff.ff+edge[id],id};
                if(carry > resp[pai[id]].ss){
                    if(carry >= resp[pai[id]].ff){
                        swap(resp[pai[id]].ff,resp[pai[id]].ss);
                        resp[pai[id]].ff = carry;
                    } else resp[pai[id]].ss = carry;
                }
            }   

            

            ans+=resp[pai[id]].ff.ff+resp[pai[id]].ss.ff;
            ans%=MOD;

            id = pai[id];
        }
        assert(ans>=0);
        cout << ans << '\n';
    }
    

}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45