Submission #1225729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225729		Sir_Ahmed_Imran	Arboras (RMI20_arboras)	C++17	0 / 100	5093 ms	31812 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 add insert
#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)

int M = 1e9 + 7;

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

int sub(int x, ll y){
    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];
set<pll> d[N];
vector<int> a[N];

void dfs(int v){
    for(auto & i : a[v]){
        dfs(i);
        s[v].add({l[i], i});
        d[v].add({dp[i], i});
    }
    ll x;
    l[v] = w[v];
    if(s[v].size() > 1){
        x = (*s[v].rbegin()).ff;
        x += (*--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);
        dp[v] = max(dp[v], (*d[v].rbegin()).ff);
    }
    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});
        d[p[v]].erase({dp[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);
        dp[v] = max(dp[v], (*d[v].rbegin()).ff);
    }
    if(v){
        s[p[v]].add({l[v], v});
        d[p[v]].add({dp[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