| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 948007 |
2024-03-17T12:18:28 Z |
huutuan |
Arboras (RMI20_arboras) |
C++14 |
|
317 ms |
50516 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19444 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
41460 KB |
Output is correct |
| 2 |
Correct |
89 ms |
40404 KB |
Output is correct |
| 3 |
Correct |
148 ms |
40788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
317 ms |
44268 KB |
Output is correct |
| 2 |
Correct |
188 ms |
48084 KB |
Output is correct |
| 3 |
Correct |
128 ms |
42320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19444 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 4 |
Correct |
227 ms |
41460 KB |
Output is correct |
| 5 |
Correct |
89 ms |
40404 KB |
Output is correct |
| 6 |
Correct |
148 ms |
40788 KB |
Output is correct |
| 7 |
Correct |
317 ms |
44268 KB |
Output is correct |
| 8 |
Correct |
188 ms |
48084 KB |
Output is correct |
| 9 |
Correct |
128 ms |
42320 KB |
Output is correct |
| 10 |
Correct |
315 ms |
44200 KB |
Output is correct |
| 11 |
Correct |
186 ms |
48076 KB |
Output is correct |
| 12 |
Correct |
146 ms |
42324 KB |
Output is correct |
| 13 |
Correct |
302 ms |
49400 KB |
Output is correct |
| 14 |
Correct |
269 ms |
50516 KB |
Output is correct |
