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 |