답안 #948005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948005 2024-03-17T12:02:42 Z huutuan Arboras (RMI20_arboras) C++14
55 / 100
336 ms 50460 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){
         val.first%=mod;
         t[k].val.first=(t[k].val.first+(r-l+1)*val.first)%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)%mod+mod)%mod;
         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;
         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 247 ms 41496 KB Output is correct
2 Correct 91 ms 40516 KB Output is correct
3 Correct 123 ms 41040 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 44156 KB Output is correct
2 Correct 182 ms 50460 KB Output is correct
3 Correct 132 ms 44628 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 247 ms 41496 KB Output is correct
5 Correct 91 ms 40516 KB Output is correct
6 Correct 123 ms 41040 KB Output is correct
7 Correct 310 ms 44156 KB Output is correct
8 Correct 182 ms 50460 KB Output is correct
9 Correct 132 ms 44628 KB Output is correct
10 Correct 336 ms 46216 KB Output is correct
11 Correct 185 ms 50280 KB Output is correct
12 Incorrect 144 ms 44372 KB Output isn't correct
13 Halted 0 ms 0 KB -