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 |