Submission #850895

#TimeUsernameProblemLanguageResultExecution timeMemory
850895alexddArboras (RMI20_arboras)C++17
24 / 100
5097 ms10576 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int n;
int parent[100005];
int cost[100005];
pair<int,int> maxd[100005];
vector<int> con[100005];
int sum=0;
void process_update(int a, int b)
{
    int old = maxd[a].first, aux, oldcost = cost[a];
    cost[a]+=b;
    //cout<<a<<" "<<cost[a]<<" zzz\n";
    for(int j=a;j!=1;j=parent[j])
    {
        aux = maxd[parent[j]].first;

        sum = (sum + MOD - (maxd[parent[j]].first + maxd[parent[j]].second)%MOD)%MOD;

        if(maxd[parent[j]].first <= maxd[j].first + cost[j])
        {
            if(maxd[parent[j]].first != old + oldcost)
                maxd[parent[j]].second = maxd[parent[j]].first;
            maxd[parent[j]].first = maxd[j].first + cost[j];
        }
        else if(maxd[parent[j]].second < maxd[j].first + cost[j])
        {
            maxd[parent[j]].second = maxd[j].first + cost[j];
        }
        //cout<<parent[j]<<"   "<<maxd[parent[j]].first<<" "<<maxd[parent[j]].second<<"   "<<old<<" "<<oldcost<<"\n";
        sum = (sum + (maxd[parent[j]].first + maxd[parent[j]].second)%MOD)%MOD;
        old=aux;
        oldcost=cost[parent[j]];
    }
    //cout<<"   ";
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    int a;
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        a++;
        parent[i]=a;
        con[parent[i]].push_back(i);
    }
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        process_update(i,a);
    }
    cout<<sum<<"\n";
    int cntq,b;
    cin>>cntq;
    for(int i=0;i<cntq;i++)
    {
        cin>>a>>b;
        a++;
        process_update(a,b);
        cout<<sum<<"\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...