107702024-04-11 17:22:58111Gyors utakcpp17Wrong answer 0/100201ms38996 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()<<'\n';
	while(Q--){
		int i;
		cin>>i;
		i++;
		st.update(ti[i],to[i]-1);
		cout<<ans()<<'\n';
	}
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1824 KiB
2Wrong answer4ms3008 KiB
subtask20/10
3Wrong answer3ms2296 KiB
4Wrong answer3ms2360 KiB
5Wrong answer3ms2688 KiB
6Wrong answer3ms2744 KiB
7Wrong answer3ms2760 KiB
8Wrong answer3ms2920 KiB
subtask30/11
9Wrong answer3ms2296 KiB
10Wrong answer3ms2360 KiB
11Wrong answer3ms2688 KiB
12Wrong answer3ms2744 KiB
13Wrong answer3ms2760 KiB
14Wrong answer3ms2920 KiB
15Wrong answer6ms3636 KiB
16Wrong answer6ms3540 KiB
17Wrong answer6ms3448 KiB
18Wrong answer4ms3428 KiB
19Wrong answer6ms3708 KiB
20Wrong answer4ms3636 KiB
21Wrong answer6ms3800 KiB
22Wrong answer6ms3796 KiB
23Wrong answer6ms4076 KiB
24Wrong answer6ms4340 KiB
subtask40/21
25Wrong answer172ms38800 KiB
26Wrong answer175ms38796 KiB
27Wrong answer188ms38720 KiB
28Wrong answer160ms38752 KiB
29Wrong answer181ms38996 KiB
30Wrong answer184ms38988 KiB
subtask50/24
31Wrong answer3ms4276 KiB
32Wrong answer12ms6472 KiB
33Wrong answer93ms27600 KiB
34Wrong answer174ms27600 KiB
subtask60/34
35Wrong answer3ms2296 KiB
36Wrong answer3ms2360 KiB
37Wrong answer3ms2688 KiB
38Wrong answer3ms2744 KiB
39Wrong answer3ms2760 KiB
40Wrong answer3ms2920 KiB
41Wrong answer6ms3636 KiB
42Wrong answer6ms3540 KiB
43Wrong answer6ms3448 KiB
44Wrong answer4ms3428 KiB
45Wrong answer6ms3708 KiB
46Wrong answer4ms3636 KiB
47Wrong answer6ms3800 KiB
48Wrong answer6ms3796 KiB
49Wrong answer6ms4076 KiB
50Wrong answer6ms4340 KiB
51Wrong answer172ms38800 KiB
52Wrong answer175ms38796 KiB
53Wrong answer188ms38720 KiB
54Wrong answer160ms38752 KiB
55Wrong answer181ms38996 KiB
56Wrong answer184ms38988 KiB
57Wrong answer3ms4276 KiB
58Wrong answer12ms6472 KiB
59Wrong answer93ms27600 KiB
60Wrong answer174ms27600 KiB
61Wrong answer179ms28136 KiB
62Wrong answer165ms27184 KiB
63Wrong answer168ms27556 KiB
64Wrong answer168ms27192 KiB
65Wrong answer184ms28628 KiB
66Wrong answer187ms28596 KiB
67Wrong answer182ms28740 KiB
68Wrong answer193ms28684 KiB
69Wrong answer150ms26340 KiB
70Wrong answer193ms28700 KiB
71Wrong answer148ms26168 KiB
72Wrong answer186ms29136 KiB
73Wrong answer189ms29452 KiB
74Wrong answer122ms29316 KiB
75Wrong answer201ms28628 KiB
76Wrong answer184ms28772 KiB
77Wrong answer162ms27012 KiB