Submission #398526

#	Time	Username	Problem	Language	Result	Execution time	Memory
398526		model_code	Arboras (RMI20_arboras)	C++17	24 / 100	5050 ms	12624 KiB

arboras

/**
* user:  apostol-089
* fname: Daniel Ilie
* lname: Apostol
* task:  Arboras
* score: 24.0
* date:  2020-12-04 10:35:17.572833
*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back

const int N = 1e5;
const int MOD = 1e9 + 7;
vector <int> gr[1 + N];
pair <ll, int> dp[1 + N][2];
int ans;
ll d[1 + N];
int p[1 + N];
void add (int &a, ll b) {
    b %= MOD;
    a += b;
    if (a >= MOD)
        a -= MOD;
    if (a < 0)
        a += MOD;
}
void prec (int node) {
    vector <pair <ll, int>> v;
    for (int son : gr[node]) {
        prec (son);
        v.pb ({dp[son][0].first + d[son], son});
    }
    sort (v.begin (), v.end ());
    if (v.size () > 0) {
        dp[node][0] = v.back ();
    }
    if (v.size () > 1)
        dp[node][1] = v[v.size () - 2];
    add (ans, dp[node][0].first);
    add (ans, dp[node][1].first);
}
int main () {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
        cin >> p[i], p[i]++;
    for (int i = 2; i <= n; i++) {
        cin >> d[i];
        gr[p[i]].pb (i);
    }
    prec (1);
    cout << ans << "\n";
    int q;
    cin >> q;
    while (q--) {
        int v, to_add;
        cin >> v >> to_add; v++;
        d[v] += to_add;
        while (v != 1) {
            int par = p[v];
            ll lstans = 0;
            add (ans, -dp[par][0].first);
            add (ans, -dp[par][1].first);
            if (dp[par][0].second == v)  {
                dp[par][0].first = dp[v][0].first + d[v];
            }
            else {
                if (dp[v][0].first + d[v] >= dp[par][0].first) {
                    dp[par][1] = dp[par][0];
                    dp[par][0] = {dp[v][0].first + d[v], v};
                }
                else {
                    if (dp[v][0].first + d[v] >= dp[par][1].first)
                        dp[par][1] = {dp[v][0].first + d[v], v};
                }
            }
            add (ans, dp[par][0].first);
            add (ans, dp[par][1].first);
            if (ans == lstans) break;
            v = par;
        }
        cout << ans << "\n";
    }
    return 0;
}

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