Submission #1297734

#TimeUsernameProblemLanguageResultExecution timeMemory
1297734MisterReaperArboras (RMI20_arboras)C++20
100 / 100
316 ms22004 KiB
// File C.cpp created on 01.12.2025 at 14:24:02
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int md = int(1E9) + 7;

int add(int x, int y) {
    x += y;
    if (x >= md) {
        x -= md;
    }
    return x;
}
int sub(int x, int y) {
    x -= y;
    if (x < 0) {
        x += md;
    }
    return x;
}
int mul(int x, int y) {
    return 1LL * x * y % md;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
    struct node {
        int siz = 1;
        i64 act = 0;
        int sum = 0;
        i64 lz = 0;
        node() {}
        node(i64 x) : act(x), sum(x % md) {}
        void modify(i64 x) {
            act += x;
            sum = add(sum, mul(x % md, siz));
            lz += x;
        }
    };
    node unite(const node& lhs, const node& rhs) {
        node res;
        res.siz = lhs.siz + rhs.siz;
        res.sum = add(lhs.sum, rhs.sum);
        return res;
    }
    int n;
    std::vector<node> tree;
    segtree() {}
    void init(int n_) {
        n = n_;
        tree.resize(n << 1);
        auto dfs = [&](auto&& self, int v, int l, int r) -> void {
            if (l == r) {
                return;
            }
            def;
            self(self, lv, l, mid);
            self(self, rv, mid + 1, r);
            tree[v] = unite(tree[lv], tree[rv]);
        };
        dfs(dfs, 0, 0, n - 1);
    }
    void push(int v, int l, int r) {
        def;
        tree[lv].modify(tree[v].lz);
        tree[rv].modify(tree[v].lz);
        tree[v].lz = 0;
    }
    void set(int v, int l, int r, int p, i64 x) {
        if (l == r) {
            tree[v] = x;
            return;
        }
        def;
        push(v, l, r);
        if (p <= mid) {
            set(lv, l, mid, p, x);
        } else {
            set(rv, mid + 1, r, p, x);
        }
        tree[v] = unite(tree[lv], tree[rv]);
    }
    void set(int p, i64 x) {
        set(0, 0, n - 1, p, x);
    }
    void modify(int v, int l, int r, int ql, int qr, i64 x) {
        if (ql == l && r == qr) {
            tree[v].modify(x);
            return;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            modify(lv, l, mid, ql, qr, x);
        } else if (mid + 1 <= ql) {
            modify(rv, mid + 1, r, ql, qr, x);
        } else {
            modify(lv, l, mid, ql, mid, x);
            modify(rv, mid + 1, r, mid + 1, qr, x);
        }
        tree[v] = unite(tree[lv], tree[rv]);
    }
    void modify(int l, int r, i64 x) {
        modify(0, 0, n - 1, l, r, x);
    }
    i64 get(int v, int l, int r, int p) {
        if (l == r) {
            return tree[v].act;
        }
        def;
        push(v, l, r);
        if (p <= mid) {
            return get(lv, l, mid, p);
        } else {
            return get(rv, mid + 1, r, p);
        }
    }
    i64 get(int p) {
        return get(0, 0, n - 1, p);
    }
    int sum() {
        return tree[0].sum;
    }
} seg;
struct fenwick {
    int n;
    std::vector<int> tree;
    fenwick() {}
    void init(int n_) {
        n = n_;
        tree.resize(n + 1);
    }
    void modify(int p, int x) {
        for (p += 1; p <= n; p += p & -p) {
            tree[p] += x;
        }
    }
    int get(int p) {
        int res = 0;
        for (p += 1; p; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
} aux;

int N;
std::vector<int> par;
std::vector<i64> dis;
std::vector<std::vector<int>> adj;

std::vector<i64> mx2;
std::vector<int> heavy;

std::vector<int> siz;
std::vector<int> top;
std::vector<int> tin;
std::vector<int> tout;
std::vector<int> tour;

int tim; 

void dfs1(int v) {
    siz[v] = 1;
    for (auto& u : adj[v]) {
        dfs1(u);
        siz[v] += siz[u];
        if (siz[u] > siz[adj[v][0]]) {
            std::swap(u, adj[v][0]);
        }
    }
}

void dfs2(int v) {
    tour[tim] = v;
    tin[v] = tim++;
    for (auto u : adj[v]) {
        top[u] = (u == adj[v][0] ? top[v] : u);
        dfs2(u);
    }
    tout[v] = tim - 1;
    if (siz[v] != 1) {
        heavy[v] = adj[v][0];
        aux.modify(tin[heavy[v]], +1);
    }
}

void init() {
    dfs1(0);
    dfs2(0);
}

i64 ans = 0;

void upd(int v, i64 x) {
    while (v != 0) {
        int u = par[v];
        if (heavy[u] == v) {
            int w = top[u];
            if (u == w) {
                seg.modify(tin[u], tin[u], x);
                v = u;
            } else {
                if (aux.get(tin[w] + 1, tin[u]) == tin[u] - tin[w]) {
                    seg.modify(tin[w], tin[u], x);
                    v = w;
                } else {
                    int len = tin[u] - tin[w];
                    int lo = 0, hi = len - 1;
                    while (lo < hi) {
                        int mid = (lo + hi + 1) >> 1;
                        int vrt = tour[tin[u] - mid];
                        if (aux.get(tin[vrt] + 1, tin[u]) == tin[u] - tin[vrt]) {
                            lo = mid;
                        } else {
                            hi = mid - 1;
                        }
                    }
                    w = tour[tin[u] - lo];
                    seg.modify(tin[w], tin[u], x);
                    v = w;
                }
            }
        } else {
            i64 dv = seg.get(tin[v]);
            i64 du = seg.get(tin[u]);
            if (dv + dis[v] > du) {
                ans -= mx2[u];
                mx2[u] = du;
                ans += mx2[u];
                seg.set(tin[u], dv + dis[v]);
                x = dv + dis[v] - du;
                aux.modify(tin[heavy[u]], -1);
                heavy[u] = v;
                aux.modify(tin[v], +1);
                v = u;
            } else if (dv + dis[v] > mx2[u]) {
                ans -= mx2[u];
                mx2[u] = dv + dis[v];
                ans += mx2[u];
                break;
            } else {
                break;
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N;

    par.resize(N);
    dis.resize(N);
    adj.resize(N);

    seg.init(N);
    aux.init(N);
    mx2.resize(N);
    heavy.resize(N);

    top.resize(N);
    siz.resize(N);
    tin.resize(N);
    tout.resize(N);
    tour.resize(N);

    for (int i = 1; i < N; ++i) {
        std::cin >> par[i];
        adj[par[i]].emplace_back(i);
    }

    init();

    for (int i = 1; i < N; ++i) {
        std::cin >> dis[i];
        upd(i, dis[i]);
    }

    std::cout << add(ans % md, seg.sum()) << '\n';

    int Q;
    std::cin >> Q;

    while (Q--) {
        int v, x;
        std::cin >> v >> x;
        dis[v] += x;
        upd(v, x);
        std::cout << add(ans % md, seg.sum()) << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...