Submission #1225774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225774		Ghulam_Junaid	Arboras (RMI20_arboras)	C++20	24 / 100	5094 ms	16344 KiB

arboras

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10, LG = 17, mod = 1e9 + 7;
int n, par[N][LG], q, mx[N][2];
ll d[N], dep[N], val[N], ans;
vector<int> g[N];

void dfs(int v){
    for (int u : g[v]){
        dfs(u);
        dep[v] = max(dep[v], dep[u] + d[u]);
        
        if (d[mx[v][1]] + dep[mx[v][1]] < d[u] + dep[u])
            mx[v][1] = u;
        if (d[mx[v][0]] + dep[mx[v][0]] < d[mx[v][1]] + dep[mx[v][1]])
            swap(mx[v][0], mx[v][1]);
    }
    val[v] = d[mx[v][0]] + dep[mx[v][0]] + d[mx[v][1]] + dep[mx[v][1]];
    ans += val[v];
    ans %= mod;
}

void upd(int u){
    if (!u) return;
    int v = par[u][0];
    
    int prv = val[v];
    ans -= val[v];

    if (mx[v][0] == u)
        val[v] = d[mx[v][0]] + dep[mx[v][0]] + d[mx[v][1]] + dep[mx[v][1]];
    else if (mx[v][1] == u){
        val[v] = d[mx[v][0]] + dep[mx[v][0]] + d[mx[v][1]] + dep[mx[v][1]];
        if (d[mx[v][0]] + dep[mx[v][0]] < d[mx[v][1]] + dep[mx[v][1]])
            swap(mx[v][0], mx[v][1]);
    }
    else{
        if (d[mx[v][1]] + dep[mx[v][1]] < d[u] + dep[u])
            mx[v][1] = u;
        if (d[mx[v][0]] + dep[mx[v][0]] < d[mx[v][1]] + dep[mx[v][1]])
            swap(mx[v][0], mx[v][1]);
        val[v] = d[mx[v][0]] + dep[mx[v][0]] + d[mx[v][1]] + dep[mx[v][1]];
    }
    ans += val[v];
    ans %= mod;
    ans += mod;
    ans %= mod;

    dep[v] = max(dep[v], dep[u] + d[u]);
    if (val[v] > prv) upd(v);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i < n; i ++)
        cin >> par[i][0], g[par[i][0]].push_back(i);
    for (int i = 1; i < n; i ++)
        cin >> d[i];
    for (int v = 0; v < n; v ++)
        mx[v][0] = mx[v][1] = n;
    dfs(0);

    cout << ans << '\n';
    cin >> q;
    while (q--){
        int v, x;
        cin >> v >> x;
        d[v] += x;
        upd(v);
        cout << ans << '\n';
    }
}

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