제출 #948007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948007		huutuan	Arboras (RMI20_arboras)	C++14	100 / 100	317 ms	50516 KiB

arboras

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int mod=1e9+7;

struct FenwickTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   void update(int l, int r, int val){
      update(l, val);
      if (r<n) update(r+1, -val);
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
} bit;

struct Node{
   pair<int, int> val, lazy;
   Node (pair<int, int> _val={0, 0}){
      val=_val;
      lazy={0, 0};
   }
   Node operator+(const Node &b){
      return Node({(val.first+b.val.first)%mod, val.second});
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int l, int r, pair<int, int> val){
      if (l!=r) t[k].val.first=(t[k].val.first+(r-l+1)*(val.first%mod))%mod;
      else t[k].val.first=(t[k].val.first+(r-l+1)*val.first);
      t[k].val.second=val.second;
      t[k].lazy.first=(t[k].lazy.first+val.first);
      t[k].lazy.second=val.second;
   }
   void push(int k, int l, int r){
      if (t[k].lazy.second){
         int mid=(l+r)>>1;
         apply(k<<1, l, mid, t[k].lazy);
         apply(k<<1|1, mid+1, r, t[k].lazy);
         t[k].lazy={0, 0};
      }
   }
   void update(int k, int l, int r, int L, int R, pair<int, int> val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, l, r, val);
         return;
      }
      push(k, l, r);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   Node get(int k, int l, int r, int pos){
      if (l==r) return t[k];
      push(k, l, r);
      int mid=(l+r)>>1;
      if (pos<=mid) return get(k<<1, l, mid, pos);
      return get(k<<1|1, mid+1, r, pos);
   }
} st;

const int N=1e5+10, LG=17;
int n, q, par[N], dpar[N], dis[N], dep[N], up[LG][N], tin[N], tout[N], tdfs, sz[N];
pair<int, int> dist1[N], dist2[N];
int ans=0;
int head[N];
vector<int> g[N];

void dfs_sz(int u){
   sz[u]=1;
   for (int &v:g[u]){
      dfs_sz(v);
      sz[u]+=sz[v];
      if (sz[v]>sz[g[u][0]]) swap(v, g[u][0]);
   }
}

void dfs(int u, int h){
   head[u]=h;
   tin[u]=++tdfs;
   dep[u]=dep[par[u]]+1;
   for (int k=1; k<LG; ++k) up[k][u]=up[k-1][up[k-1][u]];
   pair<int, int> d1, d2;
   if (g[u].empty()) d1={0, u};
   for (int v:g[u]){
      dis[v]=dis[u]+dpar[v];
      up[0][v]=u;
      dfs(v, v==g[u][0]?h:v);
      pair<int, int> dd={dist1[v].first+dpar[v], dist1[v].second};
      if (d1<dd) d2=d1, d1=dd;
      else d2=max(d2, dd);
   }
   dist1[u]=d1; dist2[u]=d2;
   tout[u]=tdfs;
}

int lift(int u, int d){
   for (int k=0; k<LG; ++k){
      if (d>>k&1) u=up[k][u];
   }
   return u;
}

int get_dist(int u, int v){
   return bit.get(tin[v])-bit.get(tin[u]);
}

void update(int u, int v, pair<int, int> d){
   while (head[u]!=head[v]){
      if (dep[head[u]]>dep[head[v]]) swap(u, v);
      st.update(1, 1, n, tin[head[v]], tin[v], d);
      v=par[head[v]];
   }
   if (tin[u]>tin[v]) swap(u, v);
   st.update(1, 1, n, tin[u], tin[v], d);
}

int32_t main(){
   #ifdef sus
   freopen("C.inp", "r", stdin);
   freopen("C.out", "w", stdout);
   #endif
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=2; i<=n; ++i) cin >> par[i], ++par[i], g[par[i]].push_back(i);
   for (int i=2; i<=n; ++i) cin >> dpar[i];
   dfs_sz(1);
   dfs(1, 1);
   st.init(n);
   bit.init(n);
   for (int i=1; i<=n; ++i){
      ans=(ans+dist1[i].first)%mod;
      ans=(ans+dist2[i].first)%mod;
      bit.update(tin[i], tin[i], dis[i]);
      st.update(1, 1, n, tin[i], tin[i], dist1[i]);
   }
   cout << ans << '\n';
   cin >> q;
   while (q--){
      int u, d; cin >> u >> d; ++u;
      bit.update(tin[u], tout[u], d);
      int w=st.get(1, 1, n, tin[u]).val.second;
      u=par[u];
      int cnt=0;
      while (u){
         auto p=st.get(1, 1, n, tin[u]).val;
         pair<int, int> tmp={get_dist(u, w), w};
         if (p>tmp){
            if (tmp>=dist2[u]){
               ans=(ans-dist2[u].first%mod+mod)%mod;
               dist2[u]=tmp;
               ans=(ans+dist2[u].first)%mod;
            }
            break;
         }
         int diff=tmp.first-p.first;
         int v=u;
         for (int k=LG-1; k>=0; --k) if (up[k][u]){
            int u2=up[k][u];
            auto p2=st.get(1, 1, n, tin[u2]).val;
            if (p2<=make_pair(get_dist(u2, w), w) && p2.second==p.second) u=u2;
         }
         ans=(ans+(dep[v]-dep[u]+1)*(diff%mod))%mod;
         ans=(ans-dist2[v].first%mod+mod)%mod;
         if (p.second!=w) dist2[v]=p;
         ans=(ans+dist2[v].first)%mod;
         update(u, v, {diff, w});
         ++cnt;
         u=par[u];
      }
      cout << ans << '\n';
   }
   return 0;
}

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