107702024-04-11 17:22:58111Gyors utakcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1824 KiB
2Hibás válasz4ms3008 KiB
subtask20/10
3Hibás válasz3ms2296 KiB
4Hibás válasz3ms2360 KiB
5Hibás válasz3ms2688 KiB
6Hibás válasz3ms2744 KiB
7Hibás válasz3ms2760 KiB
8Hibás válasz3ms2920 KiB
subtask30/11
9Hibás válasz3ms2296 KiB
10Hibás válasz3ms2360 KiB
11Hibás válasz3ms2688 KiB
12Hibás válasz3ms2744 KiB
13Hibás válasz3ms2760 KiB
14Hibás válasz3ms2920 KiB
15Hibás válasz6ms3636 KiB
16Hibás válasz6ms3540 KiB
17Hibás válasz6ms3448 KiB
18Hibás válasz4ms3428 KiB
19Hibás válasz6ms3708 KiB
20Hibás válasz4ms3636 KiB
21Hibás válasz6ms3800 KiB
22Hibás válasz6ms3796 KiB
23Hibás válasz6ms4076 KiB
24Hibás válasz6ms4340 KiB
subtask40/21
25Hibás válasz172ms38800 KiB
26Hibás válasz175ms38796 KiB
27Hibás válasz188ms38720 KiB
28Hibás válasz160ms38752 KiB
29Hibás válasz181ms38996 KiB
30Hibás válasz184ms38988 KiB
subtask50/24
31Hibás válasz3ms4276 KiB
32Hibás válasz12ms6472 KiB
33Hibás válasz93ms27600 KiB
34Hibás válasz174ms27600 KiB
subtask60/34
35Hibás válasz3ms2296 KiB
36Hibás válasz3ms2360 KiB
37Hibás válasz3ms2688 KiB
38Hibás válasz3ms2744 KiB
39Hibás válasz3ms2760 KiB
40Hibás válasz3ms2920 KiB
41Hibás válasz6ms3636 KiB
42Hibás válasz6ms3540 KiB
43Hibás válasz6ms3448 KiB
44Hibás válasz4ms3428 KiB
45Hibás válasz6ms3708 KiB
46Hibás válasz4ms3636 KiB
47Hibás válasz6ms3800 KiB
48Hibás válasz6ms3796 KiB
49Hibás válasz6ms4076 KiB
50Hibás válasz6ms4340 KiB
51Hibás válasz172ms38800 KiB
52Hibás válasz175ms38796 KiB
53Hibás válasz188ms38720 KiB
54Hibás válasz160ms38752 KiB
55Hibás válasz181ms38996 KiB
56Hibás válasz184ms38988 KiB
57Hibás válasz3ms4276 KiB
58Hibás válasz12ms6472 KiB
59Hibás válasz93ms27600 KiB
60Hibás válasz174ms27600 KiB
61Hibás válasz179ms28136 KiB
62Hibás válasz165ms27184 KiB
63Hibás válasz168ms27556 KiB
64Hibás válasz168ms27192 KiB
65Hibás válasz184ms28628 KiB
66Hibás válasz187ms28596 KiB
67Hibás válasz182ms28740 KiB
68Hibás válasz193ms28684 KiB
69Hibás válasz150ms26340 KiB
70Hibás válasz193ms28700 KiB
71Hibás válasz148ms26168 KiB
72Hibás válasz186ms29136 KiB
73Hibás válasz189ms29452 KiB
74Hibás válasz122ms29316 KiB
75Hibás válasz201ms28628 KiB
76Hibás válasz184ms28772 KiB
77Hibás válasz162ms27012 KiB