제출 #875176

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

arboras

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
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;
void dfs(int i,int pr){
    for(auto j:adj[i]){
        if(j[0]==pr)continue;
        dfs(j[0],i);
        ans[i] = max(ans[i],ans[j[0]]);
    }
    ans[i]+=par[i].second;
    all+=ans[i];all%=mod;
}
int 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,0);
    cout<<((all-ans[0])%mod+mod)%mod<<endl;
    int q;cin>>q;
    while(q--){
        int v,e;
        cin>>v>>e;
        long long xd = ans[v]+e;
        par[v].second+=e;
        ans[v]+=e;
        all+=e;all%=mod;
        while(v!=0){
            v = par[v].first;
            xd+=par[v].second;
            all-=ans[v];all%=mod;all+=mod;all%=mod;
            ans[v] = max(ans[v],xd);
            all+=ans[v];all%=mod;
        }
        cout<<((all-ans[0])%mod+mod)%mod<<endl;
    }
    return 0;
}

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