Submission #749903

#	Time	Username	Problem	Language	Result	Execution time	Memory
749903		doowey	Arboras (RMI20_arboras)	C++14	100 / 100	187 ms	23004 KiB

arboras

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 1;
const int MOD = (int)1e9 + 7;

vector<int> E[N];
int par[N];
ll w[N];
int n;
int sub[N];
int link[N];
int rig[N];
int tin[N];
int tout[N];
int nd[N];
int tt = -1;
ll dp0[N];
int big0[N];
ll dp1[N];

void dfs(int u){
    sub[u] = 1;
    dp0[u] = dp1[u] = 0ll;
    big0[u] = -1;
    for(auto x : E[u]){
        dfs(x);
        if(dp0[x] + w[x] > dp0[u]){
            big0[u] = x;
            dp1[u] = dp0[u];
            dp0[u] = dp0[x] + w[x];
        }
        else if(dp0[x] + w[x] > dp1[u]){
            dp1[u] = dp0[x] + w[x];
        }
        sub[u] += sub[x];
    }
}


void dfs1(int u){
    tt ++ ;
    tin[u] = tt;
    nd[tin[u]] = u;
    if(link[u] == -1) link[u] = u;
    rig[link[u]] = tin[u];
    int nx = -1;
    for(auto x : E[u]){
        if(nx == -1 || sub[x] > sub[nx]){
            nx = x;
        }
    }
    if(nx != -1){
        link[nx]=link[u];
    }
    if(nx != -1){
        dfs1(nx);
    }

    for(auto x : E[u]){
        if(x != nx)
            dfs1(x);
    }
    tout[u] = tt;
}

struct Node{
    ll dp;
    int id;
};

Node T[N * 4 + 24];

ll sum = 0;

void inc(ll y){
    y %= MOD;
    sum += y;
    if(sum < 0) sum += MOD;
    else if(sum >= MOD) sum -= MOD;
}

void build(int node, int cl, int cr){
    if(cl == cr){
        if(big0[nd[cl]] == -1 || link[big0[nd[cl]]] != link[nd[cl]])
            T[node].id = cl;
        else
            T[node].id = -1;
        T[node].dp = dp0[nd[cl]];
        inc(dp0[nd[cl]] + dp1[nd[cl]]);
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node].dp = 0ll;
    T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}

int query_id(int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr) return -1;
    if(cl >= tl && cr <= tr){
        return T[node].id;
    }
    int mid = (cl + cr) / 2;
    return max(query_id(node * 2, cl, mid, tl, tr), query_id(node * 2 + 1, mid + 1, cr, tl, tr));
}

void set_id(int node, int cl, int cr, int id, int p){
    if(cl == cr){
        T[node].id = p;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        set_id(node * 2, cl, mid, id, p);
    else
        set_id(node * 2 + 1, mid + 1, cr, id, p);
    T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}

void push(int node, int cl, int cr){
    if(cl != cr){
        T[node * 2].dp += T[node].dp;
        T[node * 2 + 1].dp += T[node].dp;
        T[node].dp = 0;
    }
}

void add_dp(int node, int cl, int cr, int tl, int tr, ll W){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        inc((cr - cl + 1) * 1ll * W);
        T[node].dp += W;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    add_dp(node * 2, cl, mid, tl, tr, W);
    add_dp(node * 2 + 1, mid + 1, cr, tl, tr, W);
}

ll ask_dp(int node, int cl, int cr, int idx){
    push(node, cl, cr);
    if(cl == cr){
        return T[node].dp;
    }
    int mid = (cl + cr) / 2;
    if(mid >= idx)
        return ask_dp(node * 2, cl, mid, idx);
    else
        return ask_dp(node * 2 + 1, mid + 1, cr, idx);
}

ll get_dp(int node){
    return ask_dp(1, 0, n - 1, tin[node]);
}

ll add;

void check_up(int &v){
    ll f = get_dp(v) + w[v];
    ll par_dp = get_dp(par[v]);
    if(big0[par[v]] == v){
        add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
        v = par[v];
    }
    else{
        if(f > par_dp){
            add = f - par_dp;
            add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
            if(link[par[v]] == link[v]){
                set_id(1, 0, n - 1, tin[par[v]], -1);
            }
            else{
                set_id(1, 0, n - 1, tin[par[v]], tin[par[v]]);
            }
            inc(par_dp-dp1[par[v]]);
            dp1[par[v]] = par_dp;
            big0[par[v]] = v;
            v=par[v];
        }
        else if(f > dp1[par[v]]){
            inc(f-dp1[par[v]]);
            dp1[par[v]] = f;
            v=0;
        }
        else{
            v = 0;
        }
    }
}

ll n0[N];
ll n1[N];

void dfs2(int u){
    n0[u] = n1[u] = 0ll;
    for(auto x : E[u]){
        dfs2(x);
        if(n0[x] + w[x] > n0[u]){
            n1[u] = n0[u];
            n0[u] = n0[x] + w[x];
        }
        else if(n0[x] + w[x] > n1[u]){
            n1[u] = n0[x] + w[x];
        }
    }
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    cin >> n;
    for(int i = 1; i < n; i ++ ){
        cin >> par[i];
        E[par[i]].push_back(i);
    }
    for(int i = 1; i < n; i ++ ){
        cin >> w[i];
    }
    for(int i = 0 ; i < n; i ++ ){
        link[i] = -1;

    }
    dfs(0);
    dfs1(0);
    build(1, 0, n - 1);


    dfs2(0);
    /*
    for(int i = 0; i < n; i ++ ){
        cout << "(" << get_dp(i) << "," << dp1[i] << ") ";
    }
    cout << "\n";
    for(int i = 0 ; i < n; i ++ ){
        cout << "[" << n0[i] << "," << n1[i] << "] ";
    }
    cout << "\n";
    */
    cout << sum << "\n";
    //return 0;
    int q;
    cin >> q;
    int v;
    int g;
    int i0, i1;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> v >> add;
        // implement ze walk up
        w[v] += add;
        //check_up(v);
        while(v > 0){
            if(v == link[v]){
                check_up(v);
            }
            else{
                g = query_id(1, 0, n - 1, tin[link[v]], tin[v] - 1);
                if(g == -1){
                    add_dp(1, 0, n - 1, tin[link[v]], tin[v] - 1, add);

                    v = link[v];

                }
                else{
                    add_dp(1, 0, n - 1, g + 1, tin[v] - 1, add);

                    v=nd[g + 1];
                    check_up(v);
                }
            }
        }
        //dfs2(0);
        /*
        for(int i = 0; i < n; i ++ ){
            cout << "(" << get_dp(i) << "," << dp1[i] << ") ";
        }
        cout << "\n";
        for(int i = 0 ; i < n; i ++ ){
            cout << "[" << n0[i] << "," << n1[i] << "] ";
        }
        cout << "\n";
        */
        cout << sum << "\n";
    }
    return 0;
}

Compilation message (stderr)

arboras.cpp: In function 'int main()':
arboras.cpp:258:9: warning: unused variable 'i0' [-Wunused-variable]
  258 |     int i0, i1;
      |         ^~
arboras.cpp:258:13: warning: unused variable 'i1' [-Wunused-variable]
  258 |     int i0, i1;
      |             ^~

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