107712024-04-11 17:23:54111Gyors utakcpp17Elfogadva 100/100202ms39284 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva4ms2920 KiB
subtask210/10
3Elfogadva3ms2388 KiB
4Elfogadva3ms2340 KiB
5Elfogadva3ms2348 KiB
6Elfogadva3ms2604 KiB
7Elfogadva3ms2948 KiB
8Elfogadva3ms3036 KiB
subtask311/11
9Elfogadva3ms2388 KiB
10Elfogadva3ms2340 KiB
11Elfogadva3ms2348 KiB
12Elfogadva3ms2604 KiB
13Elfogadva3ms2948 KiB
14Elfogadva3ms3036 KiB
15Elfogadva6ms3856 KiB
16Elfogadva6ms3948 KiB
17Elfogadva6ms4260 KiB
18Elfogadva6ms4200 KiB
19Elfogadva6ms4472 KiB
20Elfogadva6ms4476 KiB
21Elfogadva6ms4412 KiB
22Elfogadva6ms4432 KiB
23Elfogadva6ms4684 KiB
24Elfogadva6ms4704 KiB
subtask421/21
25Elfogadva180ms39124 KiB
26Elfogadva168ms39192 KiB
27Elfogadva185ms39088 KiB
28Elfogadva163ms39284 KiB
29Elfogadva184ms39252 KiB
30Elfogadva184ms39260 KiB
subtask524/24
31Elfogadva3ms4652 KiB
32Elfogadva12ms7104 KiB
33Elfogadva93ms28288 KiB
34Elfogadva178ms28296 KiB
subtask634/34
35Elfogadva3ms2388 KiB
36Elfogadva3ms2340 KiB
37Elfogadva3ms2348 KiB
38Elfogadva3ms2604 KiB
39Elfogadva3ms2948 KiB
40Elfogadva3ms3036 KiB
41Elfogadva6ms3856 KiB
42Elfogadva6ms3948 KiB
43Elfogadva6ms4260 KiB
44Elfogadva6ms4200 KiB
45Elfogadva6ms4472 KiB
46Elfogadva6ms4476 KiB
47Elfogadva6ms4412 KiB
48Elfogadva6ms4432 KiB
49Elfogadva6ms4684 KiB
50Elfogadva6ms4704 KiB
51Elfogadva180ms39124 KiB
52Elfogadva168ms39192 KiB
53Elfogadva185ms39088 KiB
54Elfogadva163ms39284 KiB
55Elfogadva184ms39252 KiB
56Elfogadva184ms39260 KiB
57Elfogadva3ms4652 KiB
58Elfogadva12ms7104 KiB
59Elfogadva93ms28288 KiB
60Elfogadva178ms28296 KiB
61Elfogadva179ms28776 KiB
62Elfogadva166ms27716 KiB
63Elfogadva171ms28288 KiB
64Elfogadva174ms27872 KiB
65Elfogadva186ms29412 KiB
66Elfogadva182ms29348 KiB
67Elfogadva185ms29356 KiB
68Elfogadva187ms29416 KiB
69Elfogadva152ms27224 KiB
70Elfogadva187ms29440 KiB
71Elfogadva160ms27008 KiB
72Elfogadva194ms29932 KiB
73Elfogadva189ms30056 KiB
74Elfogadva122ms30064 KiB
75Elfogadva202ms29332 KiB
76Elfogadva185ms29264 KiB
77Elfogadva164ms27772 KiB