| 17182 | 2025-05-29 12:07:24 | Ablablabla | Gyors utak | cpp17 | Elfogadva 100/100 | 342ms | 18856 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> csucsok;
vector<ll> tin, tout;
ll ido;
void dfs(ll akt){
tin[akt] = ido;
ido++;
for(ll x : csucsok[akt]){
dfs(x);
}
tout[akt] = ido;
ido++;
}
struct segTree{
ll meret = 1;
vector<ll> fa;
vector<bool> csere;
void meretez(ll n){
while(meret < n){
meret *= 2;
}
fa.assign(2*meret - 1, 0);
csere.assign(2*meret - 1, 0);
}
ll keres(ll a, ll b, ll ind, ll kezd, ll veg){
if(veg < kezd){
return 0;
}
if(veg < a || b < kezd){
return 0;
} else if(kezd <= a && b <= veg){
return fa[ind];
}
ll k = (a + b) / 2;
ll akt = keres(a, k, 2*ind +1, kezd, veg) + keres(k + 1, b, 2*ind + 2, kezd, veg);
if(csere[ind]){
akt = (b - a + 1) - akt;
}
return akt;
}
ll valt(ll a, ll b, ll ind, ll kezd, ll veg){
if(veg < a || b < kezd){
return fa[ind];
} else if(kezd <= a && b <= veg){
fa[ind] = (b - a + 1) - fa[ind];
csere[ind] = !csere[ind];
return fa[ind];
}
ll k = (a + b) / 2;
fa[ind] = valt(a, k, 2*ind + 1, kezd, veg) + valt(k + 1, b, 2*ind + 2, kezd, veg);
if(csere[ind]){
fa[ind] = (b - a + 1) - fa[ind];
}
return fa[ind];
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, q;
cin >> n >> q;
csucsok.assign(n, vector<ll>());
tin.assign(n, 0);
tout.assign(n, 0);
for(ll i = 1; i < n; i++){
ll a;
cin >> a;
a--;
csucsok[a].push_back(i);
}
dfs(0);
segTree fa;
fa.meretez(2*n);
for(ll i = 1; i < n; i++){
ll a;
cin >> a;
if(a){
fa.valt(0, fa.meret - 1, 0, tin[i], tout[i]);
}
}
ll ps = fa.fa[0]/2;
ll pt = n - ps;
cout << (ps*(ps - 1) + pt*(pt - 1))/2 << " ";
while(q--){
ll a;
cin >> a;
fa.valt(0, fa.meret - 1, 0, tin[a], tout[a]);
ps = fa.fa[0]/2;
pt = n - ps;
cout << (ps*(ps - 1) + pt*(pt - 1))/2 << " ";
}
cout << "\n";
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| 2 | Elfogadva | 4ms | 824 KiB | ||||
| subtask2 | 10/10 | ||||||
| 3 | Elfogadva | 1ms | 420 KiB | ||||
| 4 | Elfogadva | 2ms | 532 KiB | ||||
| 5 | Elfogadva | 1ms | 588 KiB | ||||
| 6 | Elfogadva | 1ms | 316 KiB | ||||
| 7 | Elfogadva | 1ms | 508 KiB | ||||
| 8 | Elfogadva | 1ms | 316 KiB | ||||
| subtask3 | 11/11 | ||||||
| 9 | Elfogadva | 1ms | 420 KiB | ||||
| 10 | Elfogadva | 2ms | 532 KiB | ||||
| 11 | Elfogadva | 1ms | 588 KiB | ||||
| 12 | Elfogadva | 1ms | 316 KiB | ||||
| 13 | Elfogadva | 1ms | 508 KiB | ||||
| 14 | Elfogadva | 1ms | 316 KiB | ||||
| 15 | Elfogadva | 4ms | 696 KiB | ||||
| 16 | Elfogadva | 4ms | 644 KiB | ||||
| 17 | Elfogadva | 6ms | 568 KiB | ||||
| 18 | Elfogadva | 4ms | 564 KiB | ||||
| 19 | Elfogadva | 4ms | 656 KiB | ||||
| 20 | Elfogadva | 4ms | 548 KiB | ||||
| 21 | Elfogadva | 4ms | 692 KiB | ||||
| 22 | Elfogadva | 6ms | 772 KiB | ||||
| 23 | Elfogadva | 4ms | 564 KiB | ||||
| 24 | Elfogadva | 4ms | 568 KiB | ||||
| subtask4 | 21/21 | ||||||
| 25 | Elfogadva | 310ms | 18856 KiB | ||||
| 26 | Elfogadva | 305ms | 18704 KiB | ||||
| 27 | Elfogadva | 342ms | 18832 KiB | ||||
| 28 | Elfogadva | 273ms | 18832 KiB | ||||
| 29 | Elfogadva | 335ms | 18740 KiB | ||||
| 30 | Elfogadva | 333ms | 18740 KiB | ||||
| subtask5 | 24/24 | ||||||
| 31 | Elfogadva | 1ms | 500 KiB | ||||
| 32 | Elfogadva | 14ms | 1588 KiB | ||||
| 33 | Elfogadva | 104ms | 12340 KiB | ||||
| 34 | Elfogadva | 248ms | 14132 KiB | ||||
| subtask6 | 34/34 | ||||||
| 35 | Elfogadva | 1ms | 420 KiB | ||||
| 36 | Elfogadva | 2ms | 532 KiB | ||||
| 37 | Elfogadva | 1ms | 588 KiB | ||||
| 38 | Elfogadva | 1ms | 316 KiB | ||||
| 39 | Elfogadva | 1ms | 508 KiB | ||||
| 40 | Elfogadva | 1ms | 316 KiB | ||||
| 41 | Elfogadva | 4ms | 696 KiB | ||||
| 42 | Elfogadva | 4ms | 644 KiB | ||||
| 43 | Elfogadva | 6ms | 568 KiB | ||||
| 44 | Elfogadva | 4ms | 564 KiB | ||||
| 45 | Elfogadva | 4ms | 656 KiB | ||||
| 46 | Elfogadva | 4ms | 548 KiB | ||||
| 47 | Elfogadva | 4ms | 692 KiB | ||||
| 48 | Elfogadva | 6ms | 772 KiB | ||||
| 49 | Elfogadva | 4ms | 564 KiB | ||||
| 50 | Elfogadva | 4ms | 568 KiB | ||||
| 51 | Elfogadva | 310ms | 18856 KiB | ||||
| 52 | Elfogadva | 305ms | 18704 KiB | ||||
| 53 | Elfogadva | 342ms | 18832 KiB | ||||
| 54 | Elfogadva | 273ms | 18832 KiB | ||||
| 55 | Elfogadva | 335ms | 18740 KiB | ||||
| 56 | Elfogadva | 333ms | 18740 KiB | ||||
| 57 | Elfogadva | 1ms | 500 KiB | ||||
| 58 | Elfogadva | 14ms | 1588 KiB | ||||
| 59 | Elfogadva | 104ms | 12340 KiB | ||||
| 60 | Elfogadva | 248ms | 14132 KiB | ||||
| 61 | Elfogadva | 230ms | 14388 KiB | ||||
| 62 | Elfogadva | 204ms | 13876 KiB | ||||
| 63 | Elfogadva | 216ms | 13972 KiB | ||||
| 64 | Elfogadva | 228ms | 13804 KiB | ||||
| 65 | Elfogadva | 237ms | 14700 KiB | ||||
| 66 | Elfogadva | 231ms | 14680 KiB | ||||
| 67 | Elfogadva | 279ms | 14640 KiB | ||||
| 68 | Elfogadva | 275ms | 14644 KiB | ||||
| 69 | Elfogadva | 197ms | 13288 KiB | ||||
| 70 | Elfogadva | 252ms | 14736 KiB | ||||
| 71 | Elfogadva | 209ms | 12992 KiB | ||||
| 72 | Elfogadva | 264ms | 14900 KiB | ||||
| 73 | Elfogadva | 238ms | 14904 KiB | ||||
| 74 | Elfogadva | 158ms | 13260 KiB | ||||
| 75 | Elfogadva | 272ms | 14552 KiB | ||||
| 76 | Elfogadva | 263ms | 14644 KiB | ||||
| 77 | Elfogadva | 204ms | 13620 KiB | ||||