Submission #1297919

#TimeUsernameProblemLanguageResultExecution timeMemory
1297919efegArboras (RMI20_arboras)C++20
11 / 100
5094 ms28928 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#define int long long
#define ld long double
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define pqueue priority_queue

typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii; 

const int INF = 1e12; 
const int MOD = 1e9 + 7;  
const int maxN = 1100;

using i64 = long long; 

template<typename T> 
using vec = vector<T>; 

int add(int x,int y){
    if (y < 0) y += MOD; 
    return (x % MOD + y % MOD) % MOD; 
}

int mul(int x,int y){
    return (x % MOD) * (y % MOD) % MOD; 
}

vec<int> p,d,depth,old;
vec<vec<int>> adj; 
vec<multiset<int,greater<int>>> sets; 

int n,q,ans;

int cal(int node){
    return *sets[node].begin() + *next(sets[node].begin()); 
}

void dfs(int node){
    for (auto x : adj[node]){
        dfs(x); 
        old[x] = depth[x] + d[x]; 
        depth[node] = max(depth[node],old[x]);
        sets[node].insert(old[x]); 
    }
} 

void update(int node){
    while (p[node] != -1){
        auto &st = sets[p[node]];  
        depth[node] = *sets[node].begin(); 
        ans = add(ans,-cal(p[node]));
        st.erase(st.find(old[node])); 
        old[node] = depth[node] + d[node]; 
        st.insert(old[node]); 
        ans = add(ans,cal(p[node])); 

        node = p[node]; 
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); 
    cin >> n; 
    adj.assign(n + 10,vec<int>()); 
    sets.assign(n + 10,multiset<int,greater<int>>()); 
    d.assign(n + 10,0); 
    p.assign(n + 10,-1); 
    old.assign(n + 10,0); 
    depth.assign(n + 10,0); 

    for (int i = 1; i < n; i++){
        int x; cin >> x; 
        p[i] = x; 
        adj[x].pb(i); 
    } 
    for (int i = 1; i < n; i++) cin >> d[i]; 
    
    for (int i = 0; i < n; i++) {
        for (int x = 0; x < 2; x++) sets[i].insert(0); 
    }
    
    dfs(0); 
    for (int i= 0; i < n; i++) ans = add(ans,cal(i)); 
    cout << ans << endl; 
    
    int q; cin >> q;
    while (q--){
        int add,v; cin >> v >> add; 
        d[v] += add; 
        update(v);
        cout << ans % MOD << endl; 
    } 
    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...