oj.uz

답안 #943574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943574 2024-03-11T15:35:21 Z abcvuitunggio Arboras (RMI20_arboras) C++17
0 / 100
 5000 ms 30080 KB 
#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]={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 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){
        lazy[node]+=val;
        st[node].first+=val;
        return;
    }
    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]);
    st[node].first+=lazy[node];
}
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];
    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 val){
    auto [mx,v]=get(1,1,n,tin[u],tout[u]);
    res=(res+(h[u]-h[nxt[v]])*val%mod)%mod;
    u=nxt[v];
}
void walk(int u, int val){
    auto [cur,V]=get(1,1,n,tin[u],tout[u]);
    jump(u,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,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';
    }
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5027 ms 12888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5061 ms 27456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5057 ms 30080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5027 ms 12888 KB Time limit exceeded
2 Halted 0 ms 0 KB -