Submission #943599

#	Time	Username	Problem	Language	Result	Execution time	Memory
943599		abcvuitunggio	Arboras (RMI20_arboras)	C++17	100 / 100	214 ms	37972 KiB

arboras

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,p[100001],d[100001],q,h[100001],tin[100001],tout[100001],pos[100001],nxt[100001],t,res,lazy[400001];
vector <int> ke[100001];
vector <pair <int, int>> ke2[100001];
pair <int, int> mx[100001][2],st[400001];
void dfs(int u){
    nxt[u]=u;
    tin[u]=++t;
    pos[t]=u;
    mx[u][0]=mx[u][1]={d[u],u};
    for (int v:ke[u]){
        h[v]=h[u]+1;
        d[v]+=d[u];
        dfs(v);
        ke2[u].push_back({tout[v],v});
        if (mx[v][0]>mx[u][0]){
            mx[u][1]=mx[u][0];
            mx[u][0]=mx[v][0];
        }
        else
            mx[u][1]=max(mx[u][1],mx[v][0]);
    }
    res=(res+mx[u][0].first+mx[u][1].first-d[u]*2)%mod;
    nxt[mx[u][0].second]=u;
    tout[u]=t;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={d[pos[l]],pos[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=max(st[node<<1],st[node<<1|1]);
}
void recompute(int node, int val){
    st[node].first+=val;
    lazy[node]+=val;
}
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    recompute(node<<1,lazy[node]);
    recompute(node<<1|1,lazy[node]);
    lazy[node]=0;
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        recompute(node,val);
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=max(st[node<<1],st[node<<1|1]);
}
pair <int, int> get(int node, int l, int r, int u, int v){
    if (l>v||r<u||l>r||u>v)
        return {0,0};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return max(get(node<<1,l,mid,u,v),get(node<<1|1,mid+1,r,u,v));
}
void jump(int &u, int v, int val){
    res=(res+(h[u]-h[v])*val%mod)%mod;
    u=nxt[v];
}
void walk(int u, int val){
    int tmp=u;
    auto [cur,V]=get(1,1,n,tin[u],tout[u]);
    jump(u,nxt[V],val);
    cur+=val;
    while (u){
        int w=p[u];
        auto [mx,v]=get(1,1,n,tin[w],tout[w]);
        int pos=lower_bound(ke2[w].begin(),ke2[w].end(),make_pair(tout[v],0LL))-ke2[w].begin();
        int c=ke2[w][pos].second;
        auto [mx2,v2]=max(get(1,1,n,tin[w],tin[c]-1),get(1,1,n,tout[c]+1,tout[w]));
        if (make_pair(cur,V)>make_pair(mx,v)){
            nxt[V]=nxt[v];
            nxt[v]=c;
            jump(u,nxt[V],cur-mx);
            res=(res+mx-mx2)%mod;
        }
        else{
            res=(res+max(cur-mx2,0LL))%mod;
            break;
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<n;i++){
        cin >> p[i];
        ke[p[i]].push_back(i);
    }
    for (int i=1;i<n;i++)
        cin >> d[i];
    dfs(0);
    build(1,1,n);
    cout << res << '\n';
    cin >> q;
    int v,add;
    while (q--){
        cin >> v >> add;
        walk(v,add);
        update(1,1,n,tin[v],tout[v],add);
        cout << res << '\n';
    }
}

Compilation message (stderr)

arboras.cpp: In function 'void walk(long long int, long long int)':
arboras.cpp:78:9: warning: unused variable 'tmp' [-Wunused-variable]
   78 |     int tmp=u;
      |         ^~~

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