제출 #875217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875217		Ahmed57	Arboras (RMI20_arboras)	C++17	0 / 100	32 ms	22096 KiB

arboras

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<array<long long,2>> adj[100001];
long long all = 0;long long ans[100001];
pair<long long,long long> par[100001];
long long mod = 1000000007;
multiset<pair<long long,int>> s[100001];
void dfs(int i){
    for(auto j:adj[i]){
        dfs(j[0]);
        if(s[j[0]].size()==0){
            s[i].insert({j[1],j[0]});
        }else{
        auto it = s[j[0]].end();it--;
        s[i].insert({(*it).first+j[1],j[0]});
        }
    }
    if(s[i].size()){
    auto it = s[i].end();
    it--;
    all+=(*it).first;
    all%=mod;
    if(s[i].size()>1){
        it--;
        all+=(*it).first;
        all%=mod;
    }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n;
    cin>>n;
    long long p[n],d[n];
    for(int i = 1;i<n;i++)cin>>p[i];
    for(int i = 1;i<n;i++){
        cin>>d[i];
        adj[p[i]].push_back({i,d[i]});
        par[i] = {p[i],d[i]};
    }
    dfs(0);
    cout<<((all)%mod+mod)%mod<<endl;
    int q;cin>>q;
    while(q--){
        int v,e;
        cin>>v>>e;
        int org = v;
        long long xd = 0,er = 0;
        if(s[v].size()){
            auto it = s[v].end();it--;
            xd = (*it).first;
        }
        er = xd;
        par[v].second+=e;
        while(v!=0){
            xd+=par[v].second;
            er+=par[v].second;
            if(v==org)er-=e;
            int le = v;
            v = par[v].first;
            if(s[v].size()){
                auto it = s[v].end();it--;
                all-=(*it).first;all%=mod;all+=mod;all%=mod;
                if(s[v].size()>1){
                    it--;
                    all-=(*it).first;all%=mod;all+=mod;all%=mod;
                }
            }
            auto it = s[v].lower_bound(make_pair(er,le));
            if(s[v].size()){
                auto lol = s[v].end();lol--;
                er = (*lol).first;
            }else er = 0;
            if(it==s[v].end()){
                cout<<"hh";
                return 0;
            }
            s[v].erase(it);
            s[v].insert({xd,le});
            if(s[v].size()){
                auto it = s[v].end();
    it--;
    all+=(*it).first;
    all%=mod;
    if(s[v].size()>1){
        it--;
        all+=(*it).first;
        all%=mod;
    }
    }
        }
cout<<((all)%mod+mod)%mod<<endl;
    }
    return 0;
}

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