10771 2024. 04. 11 17:23:54 111 Gyors utak cpp17 Elfogadva 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 4ms 2920 KiB
subtask2 10/10
3 Elfogadva 3ms 2388 KiB
4 Elfogadva 3ms 2340 KiB
5 Elfogadva 3ms 2348 KiB
6 Elfogadva 3ms 2604 KiB
7 Elfogadva 3ms 2948 KiB
8 Elfogadva 3ms 3036 KiB
subtask3 11/11
9 Elfogadva 3ms 2388 KiB
10 Elfogadva 3ms 2340 KiB
11 Elfogadva 3ms 2348 KiB
12 Elfogadva 3ms 2604 KiB
13 Elfogadva 3ms 2948 KiB
14 Elfogadva 3ms 3036 KiB
15 Elfogadva 6ms 3856 KiB
16 Elfogadva 6ms 3948 KiB
17 Elfogadva 6ms 4260 KiB
18 Elfogadva 6ms 4200 KiB
19 Elfogadva 6ms 4472 KiB
20 Elfogadva 6ms 4476 KiB
21 Elfogadva 6ms 4412 KiB
22 Elfogadva 6ms 4432 KiB
23 Elfogadva 6ms 4684 KiB
24 Elfogadva 6ms 4704 KiB
subtask4 21/21
25 Elfogadva 180ms 39124 KiB
26 Elfogadva 168ms 39192 KiB
27 Elfogadva 185ms 39088 KiB
28 Elfogadva 163ms 39284 KiB
29 Elfogadva 184ms 39252 KiB
30 Elfogadva 184ms 39260 KiB
subtask5 24/24
31 Elfogadva 3ms 4652 KiB
32 Elfogadva 12ms 7104 KiB
33 Elfogadva 93ms 28288 KiB
34 Elfogadva 178ms 28296 KiB
subtask6 34/34
35 Elfogadva 3ms 2388 KiB
36 Elfogadva 3ms 2340 KiB
37 Elfogadva 3ms 2348 KiB
38 Elfogadva 3ms 2604 KiB
39 Elfogadva 3ms 2948 KiB
40 Elfogadva 3ms 3036 KiB
41 Elfogadva 6ms 3856 KiB
42 Elfogadva 6ms 3948 KiB
43 Elfogadva 6ms 4260 KiB
44 Elfogadva 6ms 4200 KiB
45 Elfogadva 6ms 4472 KiB
46 Elfogadva 6ms 4476 KiB
47 Elfogadva 6ms 4412 KiB
48 Elfogadva 6ms 4432 KiB
49 Elfogadva 6ms 4684 KiB
50 Elfogadva 6ms 4704 KiB
51 Elfogadva 180ms 39124 KiB
52 Elfogadva 168ms 39192 KiB
53 Elfogadva 185ms 39088 KiB
54 Elfogadva 163ms 39284 KiB
55 Elfogadva 184ms 39252 KiB
56 Elfogadva 184ms 39260 KiB
57 Elfogadva 3ms 4652 KiB
58 Elfogadva 12ms 7104 KiB
59 Elfogadva 93ms 28288 KiB
60 Elfogadva 178ms 28296 KiB
61 Elfogadva 179ms 28776 KiB
62 Elfogadva 166ms 27716 KiB
63 Elfogadva 171ms 28288 KiB
64 Elfogadva 174ms 27872 KiB
65 Elfogadva 186ms 29412 KiB
66 Elfogadva 182ms 29348 KiB
67 Elfogadva 185ms 29356 KiB
68 Elfogadva 187ms 29416 KiB
69 Elfogadva 152ms 27224 KiB
70 Elfogadva 187ms 29440 KiB
71 Elfogadva 160ms 27008 KiB
72 Elfogadva 194ms 29932 KiB
73 Elfogadva 189ms 30056 KiB
74 Elfogadva 122ms 30064 KiB
75 Elfogadva 202ms 29332 KiB
76 Elfogadva 185ms 29264 KiB
77 Elfogadva 164ms 27772 KiB