oj.uz

Submission #1115920

# Submission time Handle Problem Language Result Execution time Memory
1115920 2024-11-21T04:18:31 Z underwaterkillerwhale Arboras (RMI20_arboras) C++17
100 / 100
 1077 ms 71176 KB 
#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 2e9 + 7;
const int BASE = 137;
const int szBL = 320;

inline void Sub (ll &A, ll B) {
    A -= B;
    A %= Mod;
    if (A < 0) A += Mod;
}

inline void Add (ll &A, ll B) {
    A += B;
    A %= Mod;
}

#define Gmultiset multiset<ll, greater<ll>>

int n, m, Q;
int a[N];
int P[N], D[N];
vector<pll> ke[N];
Gmultiset S[N];
int szC[N];
int tin[N], tout[N], Head[N], pa[N], par[N][25];

struct Segment_Tree_Dist {
    int m;
    ll st[N << 2], lz[N << 2], sum[N << 2];
    void init (int n) {
        m = n;
    }
    void down (int id, int l, int r) {
        int mid = l + r >> 1;
        (sum[id << 1] += lz[id] * (mid - l + 1) % Mod) %= Mod;
        (sum[id << 1 | 1] += lz[id] * (r - mid) % Mod) %= Mod;
        rep (i, id << 1, id << 1 | 1) {
            st[i] += lz[id];
            lz[i] += lz[id];
        }
        lz[id] = 0;
    }
    void update (int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id] += val;
            lz[id] += val;
            (sum[id] += val * (r - l + 1) % Mod) %= Mod;
            return;
        }
        int mid = l + r >> 1;
        down(id, l, r);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
        sum[id] = (sum[id << 1] + sum[id << 1 | 1]) % Mod;
    }
    ll get (int id, int l, int r, int u, int v) {
        if (l > v || r < u || u > v) return 0;
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        down(id, l, r);
        return max(get(id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
    }
    void update (int u, int v, ll val) {
        update (1, 1, m, u, v, val);
    }
    ll get (int u, int v) {
        return get (1, 1, m, u, v);
    }
}ST;

struct Segment_Tree_Max2 {
    ll st[N << 2], lz[N << 2], lz2[N << 2];

    void init (int n) {
        m = n;
        rep (i, 1, n << 2) lz[i] = -1;
    }
    void Push (int id, ll val) {
        if (lz[id] == -1) (lz2[id] += val) %= Mod;
        else (lz[id] += val) %= Mod;
    }
    void down (int id, int l, int r) {
        int mid = l + r >> 1;
        if (lz[id] != -1) {
            st[id << 1] = lz[id] * (mid - l + 1) % Mod;
            lz[id << 1] = lz[id];
            st[id << 1 | 1] = lz[id] * (r - mid) % Mod;
            lz[id << 1 | 1] = lz[id];
        }
        else {
            (st[id << 1] += lz2[id] * (mid - l + 1) % Mod) %= Mod;
            Push(id << 1, lz2[id]);
            (st[id << 1 | 1] += lz2[id] * (r - mid) % Mod) %= Mod;
            Push(id << 1 | 1, lz2[id]);
        }
        lz[id] = -1;
        lz2[id] = 0;
    }
    void update (int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u || u > v) return;
        if (l >= u && r <= v) {
            st[id] = val * (r - l + 1) % Mod;
            lz[id] = val;
            return;
        }
        int mid = l + r >> 1;
        down(id, l, r);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = (st[id << 1] + st[id << 1 | 1]) % Mod;
    }
    void Add (int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u || u > v) return;
        if (l >= u && r <= v) {
            (st[id] += val * (r - l + 1) % Mod) %= Mod;
            Push(id, val);
            return;
        }
        int mid = l + r >> 1;
        down(id, l, r);
        Add (id << 1, l, mid, u, v, val);
        Add (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = (st[id << 1] + st[id << 1 | 1]) % Mod;
    }
    void update (int u, int v, ll val) {
        if (u == 0) return;
        update (1, 1, m, u, v, val);
    }
    void Add (int u, int v, ll val) {
        Add (1, 1, m, u, v, val);
    }
}ST2;

void process () {
    cin >> n;
    rep (i, 2, n) cin >> P[i], ++P[i];
//    rep (i, 2, n) {
//        cout << P[i] <<" "<<i<<"\n";
//    }
    rep (i, 2, n) cin >> D[i];
    rep (i, 2, n) {
        ke[P[i]].pb({i, D[i]});
    }
    function<void(int, int)> pdfs = [&] (int u, int p) {
        szC[u] = 1;
        par[u][0] = pa[u] = p;
        rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1];
        iter (&id, ke[u]) {
            int v = id.fs;
            pdfs(v, u);
            szC[u] += szC[v];
        }
    };
    pdfs(1, 0);
    vector<ll> dp(n + 3, 0), toP(n + 3, 0), bigC(n + 3, 0); ///update toP
    ST.init(n), ST2.init(n);
    auto comp = [&] (Gmultiset &cur, int mxV) -> ll {
        ll s1 = (mxV == -1 ? 0 : dp[mxV] + toP[mxV]);
        ll s2 = (SZ(cur) < 2 ? 0 : *next(cur.begin()));
        return max(s1, s2);
    };
    auto FindMax = [&] (Gmultiset &cur) -> ll {
        return cur.empty() ? 0 : *cur.begin();
    };
    ll res = 0;
    function<void(int, int)> hld = [&] (int u, int p) {
        static int time_dfs = 0;
        tin[u] = ++time_dfs;
        Head[u] = p;
        int mxV = -1;
        iter (&id, ke[u]) {
            int v = id.fs, w = id.se;
            toP[v] = w;
            if (mxV == -1 || szC[v] > szC[mxV]) mxV = v;
        }
//        cout << u<<" "<<Head[u] <<"\n";
        bigC[u] = mxV;
        if (mxV != -1)
            hld(mxV, p);
        iter (&id, ke[u]) {
            int v = id.fs;
            if (v == mxV) continue;
            hld(v, v);
        }
        tout[u] = time_dfs;
        ST.update (tin[u], tout[u], toP[u]);
        iter (&id, ke[u]) {
            int v = id.fs, w = id.se;
            if (v != mxV) S[u].insert(dp[v] + w);
            dp[u] = max(dp[u], dp[v] + w);
        }
//        cout << u <<": \n";
//        iter (&id, S[u]) cout << id <<" ";
//        cout <<"\n";
    };

    hld(1, 1);
    function<void(int)> dfs = [&] (int u) {
        iter (&id, ke[u]) {
            int v = id.fs;
            dfs(v);
        }
        ll preVal = ST.get(tin[u], tin[u]);
        ST2.update(tin[u], tin[u], (comp(S[u], bigC[u]) + preVal) % Mod);
        Add(res, FindMax(S[u]));
    };
    dfs(1);
    cout <<((res + ST2.st[1]) % Mod - ST.sum[1] + Mod) % Mod<<"\n";
    auto Erase = [&] (Gmultiset &cur, ll W) -> void {
        assert(cur.find(W) != cur.end());
        cur.erase(cur.find(W));
    };
    ///if them chain[u] != chain[pa]
    auto Upd = [&] (int X, int Val) {
        ST.update (tin[X], tout[X], Val);
        ST2.Add(tin[X], tout[X], Val);

        auto Find = [&] (int u, ll maxx) {
            if (ST.get(tin[u], tout[u]) > maxx) return u;
            REB (i, 20, 0) {
                int cur = par[u][i];
                if (cur != 0 && ST.get(tin[cur], tout[cur]) <= maxx) {
                    u = cur;
                }
            }
            return pa[u];
        };
        int cur = X;
        ll maxx = ST.get(tin[X], tout[X]);
        int pmax = Find(pa[cur], maxx);
//        cout << X << ": "<<pmax <<"\n";
        auto getMx = [&] (Gmultiset &cur, ll bigV) {
            ll s2 = (SZ(cur) < 2 ? 0 : *next(cur.begin()));
            return max(s2, bigV);
        };
        auto trans_phase = [&] (int u) {
            int ver = pa[u];
            if (ver == 0) return;
            assert(!S[ver].empty()); assert(bigC[ver] != -1);

            Sub(res, FindMax(S[ver]));
            Erase(S[ver], dp[u] + toP[u]);

            dp[u] = ST.get(tin[u], tout[u]) - ST.get(tin[u], tin[u]);
            if (u == X) toP[u] += Val;
            S[ver].insert(dp[u] + toP[u]);

            Add(res, FindMax(S[ver]));
            ll preVal = ST.get(tin[ver], tin[ver]);
            ll dpbigC = ST.get(tin[bigC[ver]], tout[bigC[ver]]) - preVal;
//            cout << "hihi: "<<ver<<" "<<FindMax(S[ver])<<" "<<getMx(S[ver], dpbigC)<<"\n";
            ST2.update(tin[ver], tin[ver], (getMx(S[ver], dpbigC) % Mod + preVal) % Mod);
        };

        while (Head[cur] != Head[pmax]) {
            ST2.update(tin[Head[cur]], tin[pa[cur]], maxx);
            trans_phase(Head[cur]);
            cur = pa[Head[cur]];
        }

        assert(bigC[pmax] != -1);
        ST2.update(tin[pmax] + 1, tin[pa[cur]], maxx);
        ll preVal = ST.get(tin[pmax], tin[pmax]);
        ll dpbigC = ST.get(tin[bigC[pmax]], tout[bigC[pmax]]) - preVal;
        ST2.update(tin[pmax], tin[pmax], (getMx(S[pmax], dpbigC) % Mod + preVal) % Mod); ///ko co chuyen pmax la duoi cua 1 chain
    };
    cin >> Q;
    rep (q, 1, Q) {
        ll u, val;
        cin >> u >> val;
        ++u;
        Upd(u, val);
        cout << ((res + ST2.st[1]) % Mod - ST.sum[1] + Mod) % Mod<<"\n";
    }
}

#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--) {
        process();
    }
}
/*
onepunch +27
5
0 0 1 1
0 0 0 0
8
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
*/

Compilation message

arboras.cpp: In member function 'void Segment_Tree_Dist::down(int, int, int)':
arboras.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Dist::update(int, int, int, int, int, long long int)':
arboras.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'long long int Segment_Tree_Dist::get(int, int, int, int, int)':
arboras.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::down(int, int, int)':
arboras.cpp:108:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::update(int, int, int, int, int, long long int)':
arboras.cpp:131:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::Add(int, int, int, int, int, long long int)':
arboras.cpp:144:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: At global scope:
arboras.cpp:303:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  303 | main () {
      | ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29264 KB Output is correct
2 Correct 10 ms 29264 KB Output is correct
3 Correct 8 ms 29264 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 62024 KB Output is correct
2 Correct 627 ms 63664 KB Output is correct
3 Correct 672 ms 63820 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 64840 KB Output is correct
2 Correct 493 ms 71104 KB Output is correct
3 Correct 593 ms 65440 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29264 KB Output is correct
2 Correct 10 ms 29264 KB Output is correct
3 Correct 8 ms 29264 KB Output is correct
4 Correct 845 ms 62024 KB Output is correct
5 Correct 627 ms 63664 KB Output is correct
6 Correct 672 ms 63820 KB Output is correct
7 Correct 1077 ms 64840 KB Output is correct
8 Correct 493 ms 71104 KB Output is correct
9 Correct 593 ms 65440 KB Output is correct
10 Correct 942 ms 64840 KB Output is correct
11 Correct 521 ms 71176 KB Output is correct
12 Correct 690 ms 65520 KB Output is correct
13 Correct 564 ms 67912 KB Output is correct
14 Correct 500 ms 69448 KB Output is correct