Submission #1225740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225740		Sir_Ahmed_Imran	Arboras (RMI20_arboras)	C++17	0 / 100	5089 ms	20888 KiB

arboras

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll M = 1e9 + 7;

int add(int x, ll y){
    y %= M;
    return (x + y) % M;
}

int sub(int x, ll y){
    y %= M;
    return (M + x - y) % M;
}

int ans;
ll w[N];
ll l[N];
ll dp[N];
int p[N];
set<pll> s[N];
vector<int> a[N];

void dfs(int v){
    s[v].clear();
    for(auto & i : a[v]){
        dfs(i);
        s[v].insert({l[i], i});
    }
    dp[v] = 0;
    l[v] = w[v];
    if(!a[v].empty()){
        l[v] = (*s[v].rbegin()).ff + w[v];
        dp[v] = max(dp[v], (*s[v].rbegin()).ff);
    }
    if(a[v].size() > 1){
        ll x = (*s[v].rbegin()).ff;
        x += (*next(s[v].rbegin())).ff;
        dp[v] = max(dp[v], x);
    }
    ans = add(ans, dp[v]);
}

void update(int v){
    ll x;
    ans = sub(ans, dp[v]);
    if(v) s[p[v]].erase({l[v], v});
    l[v] = w[v];
    if(a[v].size() > 1){
        x = (*s[v].rbegin()).ff;
        x += (*next(s[v].rbegin())).ff;
        dp[v] = max(dp[v], x);
    }
    if(!a[v].empty()){
        l[v] = (*s[v].rbegin()).ff + w[v];
        dp[v] = max(dp[v], (*s[v].rbegin()).ff);
    }
    if(v) s[p[v]].insert({l[v], v});
    ans = add(ans, dp[v]);
    if(v) update(p[v]);
}

void solve(){
    int n, q, v, x;
    ans = 0;
    cin >> n;
    p[0] = -1;
    for(int i = 1; i < n; i++){
        cin >> p[i];
        a[p[i]].append(i);
    }
    for(int i = 1; i < n; i++)
        cin >> w[i];
    dfs(0);
    cout << ans << nl;
    cin >> q;
    while(q--){
        cin >> v >> x;
        w[v] = add(w[v], x);
        update(v);
        cout << ans << nl;
    }
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

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