답안 #948008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948008 2024-03-17T12:19:24 Z vjudge1 Arboras (RMI20_arboras) C++14
100 / 100
324 ms 48964 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19292 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 41556 KB Output is correct
2 Correct 93 ms 40396 KB Output is correct
3 Correct 125 ms 40784 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 44124 KB Output is correct
2 Correct 173 ms 48076 KB Output is correct
3 Correct 141 ms 42324 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19292 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 255 ms 41556 KB Output is correct
5 Correct 93 ms 40396 KB Output is correct
6 Correct 125 ms 40784 KB Output is correct
7 Correct 317 ms 44124 KB Output is correct
8 Correct 173 ms 48076 KB Output is correct
9 Correct 141 ms 42324 KB Output is correct
10 Correct 324 ms 44064 KB Output is correct
11 Correct 179 ms 48280 KB Output is correct
12 Correct 149 ms 42348 KB Output is correct
13 Correct 293 ms 47892 KB Output is correct
14 Correct 267 ms 48964 KB Output is correct