oj.uz

Submission #990469

# Submission time Handle Problem Language Result Execution time Memory
990469 2024-05-30T13:31:52 Z peterandvoi Arboras (RMI20_arboras) C++17
100 / 100
 146 ms 20692 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

using ll = int64_t;

const int N = 1e5 + 5, MOD = 1e9 + 7;

int n, q;
int p[N], tin[N], tout[N], pos[N], head[N], h[N];
ll d[N];
vector<int> g[N];

using Node = pair<ll, int>;

ll lz[4 * N];
Node s[4 * N];

void bld(int id = 1, int l = 1, int r = n) {
    if (l == r) {
        s[id] = {d[pos[l]], pos[l]};
        return;
    }
    int md = (l + r) / 2;
    bld(id * 2, l, md);
    bld(id * 2 + 1, md + 1, r);
    s[id] = max(s[id * 2], s[id * 2 + 1]);
}

void app(int id, ll x) {
    s[id].first += x;
    lz[id] += x;
}

void psh(int id) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
}

void upd(int u, int v, ll x, int id = 1, int l = 1, int r = n) {
    if (u <= l && r <= v) {
        app(id, x);
        return;
    }
    if (lz[id]) {
        psh(id);
    }
    int md = (l + r) / 2;
    if (u <= md) {
        upd(u, v, x, id * 2, l, md);
    }
    if (md < v) {
        upd(u, v, x, id * 2 + 1, md + 1, r);
    }
    s[id] = max(s[id * 2], s[id * 2 + 1]);
}

Node get(int u, int v, int id = 1, int l = 1, int r = n) {
    if (u <= l && r <= v) {
        return s[id];
    }
    if (lz[id]) {
        psh(id);
    }
    int md = (l + r) / 2;
    if (u <= md && md < v) {
        return max(get(u, v, id * 2, l, md), get(u, v, id * 2 + 1, md + 1, r));
    }
    if (md < u) {
        return get(u, v, id * 2 + 1, md + 1, r);
    }
    return get(u, v, id * 2, l, md);
}

int getc(int u, int x) {
    if (u == x) {
        return u;
    }
    int l = 0, r = g[u].size() - 1, res = 0;
    while (l <= r) {
        int md = (l + r) / 2;
        if (tin[x] <= tout[g[u][md]]) {
            res = g[u][md];
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    return res;
}

ll getsec(int u, int s) {
    ll res = 0;
    if (tin[u] < tin[s]) {
        res = max(res, get(tin[u], tin[s] - 1).first);
    }
    if (tout[s] < tout[u]) {
        res = max(res, get(tout[s] + 1, tout[u]).first);
    }
    return res;
}

int order;

void dfs(int u = 1) {
    pos[tin[u] = ++order] = u;
    for (int v : g[u]) {
        d[v] += d[u];
        h[v] = h[u] + 1;
        dfs(v);
    }
    tout[u] = order;
}

void add(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> p[i];
        g[++p[i]].emplace_back(i);
    }
    for (int i = 2; i <= n; ++i) {
        cin >> d[i];
    }
    dfs();
    bld();
    int res = 0;
    iota(head + 1, head + n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        int j = get(tin[i], tout[i]).second;
        add(res, (d[j] - d[i]) % MOD);
        ll s = getsec(i, getc(i, j));
        if (s >= d[i]) {
            add(res, (s - d[i]) % MOD);
        }
        if (h[head[j]] > h[i]) {
            head[j] = i;
        }
    }
    cout << res << "\n";
    cin >> q;
    while (q--) {
        int v;
        ll a;
        cin >> v >> a;
        v++;
        int x = v, y = a;
        auto [best, id] = get(tin[v], tout[v]);
        best += a;
        while (v > 1) {
            int u = head[id];
            add(res, ll(h[v] - h[u]) * a % MOD);
            v = u;
            u = p[v];
            if (u) {
                auto [nbest, nid] = get(tin[u], tout[u]);
                assert(tin[head[nid]] <= tin[u] && tin[u] <= tout[head[nid]]);
                ll s = getc(u, nid);
                ll sec = getsec(u, s);
                if (best >= sec) {
                    add(res, (best - sec) % MOD);
                    if (make_pair(best, id) > make_pair(nbest, nid)) {
                        head[id] = head[nid];
                        head[nid] = s;
                        a = best - nbest;
                        v = u;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        upd(tin[x], tout[x], y);
        cout << res << "\n";
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6692 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 15700 KB Output is correct
2 Correct 89 ms 14548 KB Output is correct
3 Correct 104 ms 14848 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 17252 KB Output is correct
2 Correct 86 ms 20692 KB Output is correct
3 Correct 123 ms 17744 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6692 KB Output is correct
4 Correct 146 ms 15700 KB Output is correct
5 Correct 89 ms 14548 KB Output is correct
6 Correct 104 ms 14848 KB Output is correct
7 Correct 121 ms 17252 KB Output is correct
8 Correct 86 ms 20692 KB Output is correct
9 Correct 123 ms 17744 KB Output is correct
10 Correct 137 ms 19024 KB Output is correct
11 Correct 85 ms 20432 KB Output is correct
12 Correct 123 ms 17488 KB Output is correct
13 Correct 88 ms 18768 KB Output is correct
14 Correct 74 ms 19156 KB Output is correct