107712024-04-11 17:23:54111Gyors utakcpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted4ms2920 KiB
subtask210/10
3Accepted3ms2388 KiB
4Accepted3ms2340 KiB
5Accepted3ms2348 KiB
6Accepted3ms2604 KiB
7Accepted3ms2948 KiB
8Accepted3ms3036 KiB
subtask311/11
9Accepted3ms2388 KiB
10Accepted3ms2340 KiB
11Accepted3ms2348 KiB
12Accepted3ms2604 KiB
13Accepted3ms2948 KiB
14Accepted3ms3036 KiB
15Accepted6ms3856 KiB
16Accepted6ms3948 KiB
17Accepted6ms4260 KiB
18Accepted6ms4200 KiB
19Accepted6ms4472 KiB
20Accepted6ms4476 KiB
21Accepted6ms4412 KiB
22Accepted6ms4432 KiB
23Accepted6ms4684 KiB
24Accepted6ms4704 KiB
subtask421/21
25Accepted180ms39124 KiB
26Accepted168ms39192 KiB
27Accepted185ms39088 KiB
28Accepted163ms39284 KiB
29Accepted184ms39252 KiB
30Accepted184ms39260 KiB
subtask524/24
31Accepted3ms4652 KiB
32Accepted12ms7104 KiB
33Accepted93ms28288 KiB
34Accepted178ms28296 KiB
subtask634/34
35Accepted3ms2388 KiB
36Accepted3ms2340 KiB
37Accepted3ms2348 KiB
38Accepted3ms2604 KiB
39Accepted3ms2948 KiB
40Accepted3ms3036 KiB
41Accepted6ms3856 KiB
42Accepted6ms3948 KiB
43Accepted6ms4260 KiB
44Accepted6ms4200 KiB
45Accepted6ms4472 KiB
46Accepted6ms4476 KiB
47Accepted6ms4412 KiB
48Accepted6ms4432 KiB
49Accepted6ms4684 KiB
50Accepted6ms4704 KiB
51Accepted180ms39124 KiB
52Accepted168ms39192 KiB
53Accepted185ms39088 KiB
54Accepted163ms39284 KiB
55Accepted184ms39252 KiB
56Accepted184ms39260 KiB
57Accepted3ms4652 KiB
58Accepted12ms7104 KiB
59Accepted93ms28288 KiB
60Accepted178ms28296 KiB
61Accepted179ms28776 KiB
62Accepted166ms27716 KiB
63Accepted171ms28288 KiB
64Accepted174ms27872 KiB
65Accepted186ms29412 KiB
66Accepted182ms29348 KiB
67Accepted185ms29356 KiB
68Accepted187ms29416 KiB
69Accepted152ms27224 KiB
70Accepted187ms29440 KiB
71Accepted160ms27008 KiB
72Accepted194ms29932 KiB
73Accepted189ms30056 KiB
74Accepted122ms30064 KiB
75Accepted202ms29332 KiB
76Accepted185ms29264 KiB
77Accepted164ms27772 KiB