| 10713 | 2024-04-10 10:01:44 | szil | Gyors utak | cpp17 | Accepted 100/100 | 472ms | 49384 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200'001;
vector<int> g[MAXN];
int d[MAXN], timer = 1, tree[8*MAXN], lazy[8*MAXN], tin[MAXN], tout[MAXN], siz[MAXN], cnt[8*MAXN];
void push(int v) {
if (lazy[v]) {
tree[v] = cnt[v] - tree[v];
lazy[2*v] ^= 1;
lazy[2*v+1] ^= 1;
lazy[v] = 0;
}
}
void upd(int v, int tl, int tr, int l, int r) {
if (l > r) return;
push(v);
if (l == tl && r == tr) {
lazy[v] ^= 1;
push(v);
} else {
int tm = (tl + tr) / 2;
upd(2*v, tl, tm, l, min(tm, r));
upd(2*v+1, tm+1, tr, max(tm+1, l), r);
push(2*v);
push(2*v+1);
tree[v] = tree[2*v] + tree[2*v+1];
}
}
void upd2(int v, int tl, int tr, int pos) {
if (tl == tr) {
cnt[v] = 1;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
upd2(2*v, tl, tm, pos);
} else {
upd2(2*v+1, tm+1, tr, pos);
}
cnt[v] = cnt[2*v] + cnt[2*v+1];
}
}
int qry(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
push(v);
if (l == tl && r == tr) {
return tree[v];
} else {
int tm = (tl + tr) / 2;
return qry(2*v, tl, tm, l, min(tm, r)) + qry(2*v+1, tm+1, tr, max(tm+1, l), r);
}
}
void dfs(int u) {
siz[u] = 1;
tin[u] = timer++;
for (int v : g[u]) {
d[v] ^= d[u];
dfs(v);
siz[u] += siz[v];
}
tout[u] = timer++;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 2; i <= n; i++) {
int x; cin >> x;
g[x].emplace_back(i);
}
for (int i = 2; i <= n; i++) {
int x; cin >> x;
d[i] ^= x;
}
dfs(1);
for (int i = 1; i <= n; i++) {
upd2(1, 1, 2*n, tin[i]);
}
for (int i = 1; i <= n; i++) {
if (d[i]) {
upd(1, 1, 2*n, tin[i], tin[i]);
}
}
ll ans = 0;
{
int ones = tree[1];
int zeros = n-ones;
for (int i = 1; i <= n; i++) {
if (d[i]) {
ans += ones-1;
} else {
ans += zeros-1;
}
}
}
ans /= 2;
cout << ans << " ";
while (q--) {
int x; cin >> x; x++;
ll tones = tree[1];
ll tzeros = n-tones;
ll ones = qry(1, 1, 2*n, tin[x], tout[x]);
ll zeros = siz[x] - ones;
ans -= ones * (tones - ones);
ans -= zeros * (tzeros - zeros);
ans += ones * (tzeros - zeros);
ans += zeros * (tones - ones);
upd(1, 1, 2*n, tin[x], tout[x]);
cout << ans << " ";
}
cout << "\n";
return 0;
}| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 6ms | 11596 KiB | ||||
| 2 | Accepted | 9ms | 12944 KiB | ||||
| subtask2 | 10/10 | ||||||
| 3 | Accepted | 6ms | 11836 KiB | ||||
| 4 | Accepted | 6ms | 11968 KiB | ||||
| 5 | Accepted | 6ms | 12232 KiB | ||||
| 6 | Accepted | 6ms | 12444 KiB | ||||
| 7 | Accepted | 6ms | 12660 KiB | ||||
| 8 | Accepted | 6ms | 12876 KiB | ||||
| subtask3 | 11/11 | ||||||
| 9 | Accepted | 6ms | 11836 KiB | ||||
| 10 | Accepted | 6ms | 11968 KiB | ||||
| 11 | Accepted | 6ms | 12232 KiB | ||||
| 12 | Accepted | 6ms | 12444 KiB | ||||
| 13 | Accepted | 6ms | 12660 KiB | ||||
| 14 | Accepted | 6ms | 12876 KiB | ||||
| 15 | Accepted | 12ms | 13524 KiB | ||||
| 16 | Accepted | 10ms | 13380 KiB | ||||
| 17 | Accepted | 12ms | 13528 KiB | ||||
| 18 | Accepted | 10ms | 13488 KiB | ||||
| 19 | Accepted | 12ms | 13532 KiB | ||||
| 20 | Accepted | 10ms | 13480 KiB | ||||
| 21 | Accepted | 12ms | 13532 KiB | ||||
| 22 | Accepted | 12ms | 13528 KiB | ||||
| 23 | Accepted | 12ms | 13536 KiB | ||||
| 24 | Accepted | 10ms | 13376 KiB | ||||
| subtask4 | 21/21 | ||||||
| 25 | Accepted | 469ms | 49160 KiB | ||||
| 26 | Accepted | 472ms | 49152 KiB | ||||
| 27 | Accepted | 469ms | 49160 KiB | ||||
| 28 | Accepted | 469ms | 49160 KiB | ||||
| 29 | Accepted | 469ms | 49368 KiB | ||||
| 30 | Accepted | 467ms | 49384 KiB | ||||
| subtask5 | 24/24 | ||||||
| 31 | Accepted | 6ms | 13024 KiB | ||||
| 32 | Accepted | 19ms | 15852 KiB | ||||
| 33 | Accepted | 168ms | 35828 KiB | ||||
| 34 | Accepted | 301ms | 35824 KiB | ||||
| subtask6 | 34/34 | ||||||
| 35 | Accepted | 6ms | 11836 KiB | ||||
| 36 | Accepted | 6ms | 11968 KiB | ||||
| 37 | Accepted | 6ms | 12232 KiB | ||||
| 38 | Accepted | 6ms | 12444 KiB | ||||
| 39 | Accepted | 6ms | 12660 KiB | ||||
| 40 | Accepted | 6ms | 12876 KiB | ||||
| 41 | Accepted | 12ms | 13524 KiB | ||||
| 42 | Accepted | 10ms | 13380 KiB | ||||
| 43 | Accepted | 12ms | 13528 KiB | ||||
| 44 | Accepted | 10ms | 13488 KiB | ||||
| 45 | Accepted | 12ms | 13532 KiB | ||||
| 46 | Accepted | 10ms | 13480 KiB | ||||
| 47 | Accepted | 12ms | 13532 KiB | ||||
| 48 | Accepted | 12ms | 13528 KiB | ||||
| 49 | Accepted | 12ms | 13536 KiB | ||||
| 50 | Accepted | 10ms | 13376 KiB | ||||
| 51 | Accepted | 469ms | 49160 KiB | ||||
| 52 | Accepted | 472ms | 49152 KiB | ||||
| 53 | Accepted | 469ms | 49160 KiB | ||||
| 54 | Accepted | 469ms | 49160 KiB | ||||
| 55 | Accepted | 469ms | 49368 KiB | ||||
| 56 | Accepted | 467ms | 49384 KiB | ||||
| 57 | Accepted | 6ms | 13024 KiB | ||||
| 58 | Accepted | 19ms | 15852 KiB | ||||
| 59 | Accepted | 168ms | 35828 KiB | ||||
| 60 | Accepted | 301ms | 35824 KiB | ||||
| 61 | Accepted | 321ms | 35844 KiB | ||||
| 62 | Accepted | 305ms | 34468 KiB | ||||
| 63 | Accepted | 310ms | 34872 KiB | ||||
| 64 | Accepted | 310ms | 34644 KiB | ||||
| 65 | Accepted | 340ms | 36608 KiB | ||||
| 66 | Accepted | 333ms | 36404 KiB | ||||
| 67 | Accepted | 342ms | 36536 KiB | ||||
| 68 | Accepted | 347ms | 36692 KiB | ||||
| 69 | Accepted | 282ms | 33488 KiB | ||||
| 70 | Accepted | 342ms | 36684 KiB | ||||
| 71 | Accepted | 275ms | 33120 KiB | ||||
| 72 | Accepted | 354ms | 37300 KiB | ||||
| 73 | Accepted | 349ms | 37732 KiB | ||||
| 74 | Accepted | 214ms | 37732 KiB | ||||
| 75 | Accepted | 340ms | 36520 KiB | ||||
| 76 | Accepted | 338ms | 36548 KiB | ||||
| 77 | Accepted | 293ms | 34120 KiB | ||||