| 10771 | 2024-04-11 17:23:54 | 111 | Gyors utak | cpp17 | Accepted 100/100 | 202ms | 39284 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct ST{
int n;
vector<int>t,x;
ST(int n):n(n),t(n*4),x(n*4){
}
void pull(int i,int l,int r){
t[i]=t[i*2+1]+t[i*2+2];
}
void push(int i,int l,int r){
if(x[i]){
x[i]=0;
t[i*2+1]=((l+r)/2-l+1)-t[i*2+1];
t[i*2+2]=(r-(l+r)/2)-t[i*2+2];
x[i*2+1]^=1;
x[i*2+2]^=1;
}
}
void update(int i,int l,int r,int ll,int rr){
if(l>rr||r<ll){
return;
}
if(l>=ll&&r<=rr){
t[i]=(r-l+1)-t[i];
x[i]^=1;
return;
}
push(i,l,r);
update(i*2+1,l,(l+r)/2,ll,rr);
update(i*2+2,(l+r)/2+1,r,ll,rr);
pull(i,l,r);
}
void update(int ll,int rr){
update(0,0,n-1,ll,rr);
}
int query(int i,int l,int r,int ll,int rr){
if(l>rr||r<ll){
return 0;
}
if(l>=ll&&r<=rr){
return t[i];
}
push(i,l,r);
return query(i*2+1,l,(l+r)/2,ll,rr)+query(i*2+2,(l+r)/2+1,r,ll,rr);
}
int query(int ll,int rr){
return query(0,0,n-1,ll,rr);
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef CB
freopen("be1.txt","r",stdin);
// freopen("ki.txt","w",stdout);
#endif
int N,Q;
cin>>N>>Q;
vector<vector<int>>g(N+1);
for(int i=2;i<=N;i++){
int p;
cin>>p;
g[p].push_back(i);
}
vector<int>ti(N+1),to(N+1);
int t=0;
auto dfs=[&](auto self,int i)->void{
ti[i]=t++;
for(int j:g[i]){
self(self,j);
}
to[i]=t;
};
dfs(dfs,1);
ST st(N);
for(int i=2;i<=N;i++){
int w;
cin>>w;
if(w){
st.update(ti[i],to[i]-1);
}
}
auto ans=[&]()->int{
int s=st.query(0,N-1);
return s*(s-1)/2+(N-s)*(N-s-1)/2;
};
cout<<ans()<<' ';
while(Q--){
int i;
cin>>i;
i++;
st.update(ti[i],to[i]-1);
cout<<ans()<<' ';
}
cout<<'\n';
return 0;
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 3ms | 1828 KiB | ||||
| 2 | Accepted | 4ms | 2920 KiB | ||||
| subtask2 | 10/10 | ||||||
| 3 | Accepted | 3ms | 2388 KiB | ||||
| 4 | Accepted | 3ms | 2340 KiB | ||||
| 5 | Accepted | 3ms | 2348 KiB | ||||
| 6 | Accepted | 3ms | 2604 KiB | ||||
| 7 | Accepted | 3ms | 2948 KiB | ||||
| 8 | Accepted | 3ms | 3036 KiB | ||||
| subtask3 | 11/11 | ||||||
| 9 | Accepted | 3ms | 2388 KiB | ||||
| 10 | Accepted | 3ms | 2340 KiB | ||||
| 11 | Accepted | 3ms | 2348 KiB | ||||
| 12 | Accepted | 3ms | 2604 KiB | ||||
| 13 | Accepted | 3ms | 2948 KiB | ||||
| 14 | Accepted | 3ms | 3036 KiB | ||||
| 15 | Accepted | 6ms | 3856 KiB | ||||
| 16 | Accepted | 6ms | 3948 KiB | ||||
| 17 | Accepted | 6ms | 4260 KiB | ||||
| 18 | Accepted | 6ms | 4200 KiB | ||||
| 19 | Accepted | 6ms | 4472 KiB | ||||
| 20 | Accepted | 6ms | 4476 KiB | ||||
| 21 | Accepted | 6ms | 4412 KiB | ||||
| 22 | Accepted | 6ms | 4432 KiB | ||||
| 23 | Accepted | 6ms | 4684 KiB | ||||
| 24 | Accepted | 6ms | 4704 KiB | ||||
| subtask4 | 21/21 | ||||||
| 25 | Accepted | 180ms | 39124 KiB | ||||
| 26 | Accepted | 168ms | 39192 KiB | ||||
| 27 | Accepted | 185ms | 39088 KiB | ||||
| 28 | Accepted | 163ms | 39284 KiB | ||||
| 29 | Accepted | 184ms | 39252 KiB | ||||
| 30 | Accepted | 184ms | 39260 KiB | ||||
| subtask5 | 24/24 | ||||||
| 31 | Accepted | 3ms | 4652 KiB | ||||
| 32 | Accepted | 12ms | 7104 KiB | ||||
| 33 | Accepted | 93ms | 28288 KiB | ||||
| 34 | Accepted | 178ms | 28296 KiB | ||||
| subtask6 | 34/34 | ||||||
| 35 | Accepted | 3ms | 2388 KiB | ||||
| 36 | Accepted | 3ms | 2340 KiB | ||||
| 37 | Accepted | 3ms | 2348 KiB | ||||
| 38 | Accepted | 3ms | 2604 KiB | ||||
| 39 | Accepted | 3ms | 2948 KiB | ||||
| 40 | Accepted | 3ms | 3036 KiB | ||||
| 41 | Accepted | 6ms | 3856 KiB | ||||
| 42 | Accepted | 6ms | 3948 KiB | ||||
| 43 | Accepted | 6ms | 4260 KiB | ||||
| 44 | Accepted | 6ms | 4200 KiB | ||||
| 45 | Accepted | 6ms | 4472 KiB | ||||
| 46 | Accepted | 6ms | 4476 KiB | ||||
| 47 | Accepted | 6ms | 4412 KiB | ||||
| 48 | Accepted | 6ms | 4432 KiB | ||||
| 49 | Accepted | 6ms | 4684 KiB | ||||
| 50 | Accepted | 6ms | 4704 KiB | ||||
| 51 | Accepted | 180ms | 39124 KiB | ||||
| 52 | Accepted | 168ms | 39192 KiB | ||||
| 53 | Accepted | 185ms | 39088 KiB | ||||
| 54 | Accepted | 163ms | 39284 KiB | ||||
| 55 | Accepted | 184ms | 39252 KiB | ||||
| 56 | Accepted | 184ms | 39260 KiB | ||||
| 57 | Accepted | 3ms | 4652 KiB | ||||
| 58 | Accepted | 12ms | 7104 KiB | ||||
| 59 | Accepted | 93ms | 28288 KiB | ||||
| 60 | Accepted | 178ms | 28296 KiB | ||||
| 61 | Accepted | 179ms | 28776 KiB | ||||
| 62 | Accepted | 166ms | 27716 KiB | ||||
| 63 | Accepted | 171ms | 28288 KiB | ||||
| 64 | Accepted | 174ms | 27872 KiB | ||||
| 65 | Accepted | 186ms | 29412 KiB | ||||
| 66 | Accepted | 182ms | 29348 KiB | ||||
| 67 | Accepted | 185ms | 29356 KiB | ||||
| 68 | Accepted | 187ms | 29416 KiB | ||||
| 69 | Accepted | 152ms | 27224 KiB | ||||
| 70 | Accepted | 187ms | 29440 KiB | ||||
| 71 | Accepted | 160ms | 27008 KiB | ||||
| 72 | Accepted | 194ms | 29932 KiB | ||||
| 73 | Accepted | 189ms | 30056 KiB | ||||
| 74 | Accepted | 122ms | 30064 KiB | ||||
| 75 | Accepted | 202ms | 29332 KiB | ||||
| 76 | Accepted | 185ms | 29264 KiB | ||||
| 77 | Accepted | 164ms | 27772 KiB | ||||