Submission #597430

#	Time	Username	Problem	Language	Result	Execution time	Memory
597430		definitelynotmee	Arboras (RMI20_arboras)	C++98	24 / 100	5057 ms	26632 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<multiset<ll,greater<ll>>> s(n,{0,0});

    auto dfs =[&](int id, auto dfs)->void{
        for(int i : g[id]){
            dfs(i,dfs);
            s[id].insert(*s[i].begin() + edge[i]);
        }
    };
    
    dfs(0,dfs);

    ll ans = 0;

    auto calc=[&](int id){
        auto it = s[id].begin();
        ll ret = 0;
        ret+=*it;
        it++;
        ret+=*it;
        return ret;
    };

    vector<ll> resp(n);

    for(int i = 0; i < n; i++){
        resp[i] = calc(i);
        ans+=resp[i];
        ans%=MOD;
    }

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

    auto update =[&](int id, ll oldval, ll newval, auto upd)->void{
        ans-=resp[id];
        ll next = *s[id].begin();

        s[id].erase(s[id].find(oldval));
        s[id].insert(newval);

        resp[id] = calc(id);

        ans+=resp[id];
        ans%=MOD;

        // cout << "update " << id << ": " << next << ' ' << resp[id] << endl;
        // cout << "->";
        // for(ll i : s[id])
        //     cout << i << ' ';
        // cout << endl;
        if(id != 0){
            upd(pai[id],next+edge[id],*s[id].begin()+edge[id],upd);
        }
    };

    while(q--){
        ll id, x;
        cin >> id >> x;
        edge[id]+=x;
        update(pai[id],*s[id].begin()+edge[id]-x,*s[id].begin()+edge[id],update);
        cout << ans << '\n';
    }
    

}

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