#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];
}
}
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;
}
Compilation error
exit status 1
main.cpp: In function 'int main()':
main.cpp:100:19: error: 'qry' was not declared in this scope
100 | ll ones = qry(1, 1, 2*n, tin[x], tout[x]);
| ^~~
Exited with error status 1