Submission #1115830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115830		underwaterkillerwhale	Arboras (RMI20_arboras)	C++17	0 / 100	908 ms	67144 KiB

arboras

#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 getS (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return sum[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));
    }
    ll get (int u, int v) {
        return get (1, 1, m, u, v);
    }
    ll getS (int u, int v) {
        return getS (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 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;
            (lz2[id << 1] += lz2[id]) %= Mod;
            (st[id << 1 | 1] += lz2[id] * (r - mid) % Mod) %= Mod;
            (lz2[id << 1 | 1] += lz2[id]) %= Mod;
        }
        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;
            if (lz[id] == -1) (lz2[id] += val) %= Mod;
            else (lz[id] += val) %= Mod;
            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;
    }
    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) {
        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);
    }
    ll get (int u, int v) {
        return get (1, 1, m, u, v);
    }
}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;
        }
        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";
        ll preVal = ST.get(tin[u], tout[u]);
        ST2.update(tin[u], tin[u], (comp(S[u], bigC[u]) + preVal) % Mod);
        Add(res, FindMax(S[u]));
    };
    hld(1, 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 (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, ll maxx) {
            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]);
//            if (X == 5 && Val == 2) {
//                cout <<"hihihihih: "<<dp[u] <<" "<<toP[u] <<"\n";
//                iter (&id, S[ver]) cout << id <<" ";
//                cout <<"\n";
//            }
//            cout << "hihi: "<<ver<<" "<<res<<" "<<FindMax(S[ver])<<"\n";
            Add(res, FindMax(S[ver]));
            ll preVal = ST.get(tin[ver], tin[ver]);
            ll dpbigC = ST.get(tin[bigC[ver]], tin[bigC[ver]]);
            ST2.update(tin[ver], tin[ver], (getMx(S[ver], dpbigC - preVal) % Mod + preVal) % Mod);
        };
        while (Head[cur] != Head[pmax]) {
            ST2.update(tin[Head[cur]], tin[pa[cur]], maxx);
            trans_phase(Head[cur], maxx);
            cur = pa[Head[cur]];
        }
        ST2.update(tin[pmax] + 1, tin[pa[cur]], maxx);
        ll preVal = ST.get(tin[pmax], tin[pmax]);
        assert(bigC[pmax] != -1);
        ll dpbigC = ST.get(tin[bigC[pmax]], tout[bigC[pmax]]);
//        cout << X<<" "<<pmax <<" "<<bigC[pmax]<<" "<<dpbigC<<" asdasasddfff\n";
        ST2.update(tin[pmax], tin[pmax], (getMx(S[pmax], dpbigC - preVal) % 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 << u <<" "<<val<<" asdasd:\n";
//        rep (i, 1, n) cout << ST2.get(tin[i], tin[i]) <<" ";
//        cout <<"\n";
//        cout << res<<" "<<ST2.st[1]<<" "<< ST.sum[1]<<" "<<((res + ST2.st[1]) % Mod - ST.sum[1] % Mod + Mod) % Mod <<" aa\n";
        cout << ((res + ST2.st[1]) % Mod - ST.sum[1] % Mod + 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 (stderr)

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 'long long int Segment_Tree_Dist::getS(int, int, int, int, int)':
arboras.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::down(int, int, int)':
arboras.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         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:137:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |         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:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: In member function 'long long int Segment_Tree_Max2::get(int, int, int, int, int)':
arboras.cpp:160:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |         int mid = l + r >> 1;
      |                   ~~^~~
arboras.cpp: At global scope:
arboras.cpp:320:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  320 | main () {
      | ^~~~

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