10713 2024. 04. 10 10:01:44 szil Gyors utak cpp17 Elfogadva 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 6ms 11596 KiB
2 Elfogadva 9ms 12944 KiB
subtask2 10/10
3 Elfogadva 6ms 11836 KiB
4 Elfogadva 6ms 11968 KiB
5 Elfogadva 6ms 12232 KiB
6 Elfogadva 6ms 12444 KiB
7 Elfogadva 6ms 12660 KiB
8 Elfogadva 6ms 12876 KiB
subtask3 11/11
9 Elfogadva 6ms 11836 KiB
10 Elfogadva 6ms 11968 KiB
11 Elfogadva 6ms 12232 KiB
12 Elfogadva 6ms 12444 KiB
13 Elfogadva 6ms 12660 KiB
14 Elfogadva 6ms 12876 KiB
15 Elfogadva 12ms 13524 KiB
16 Elfogadva 10ms 13380 KiB
17 Elfogadva 12ms 13528 KiB
18 Elfogadva 10ms 13488 KiB
19 Elfogadva 12ms 13532 KiB
20 Elfogadva 10ms 13480 KiB
21 Elfogadva 12ms 13532 KiB
22 Elfogadva 12ms 13528 KiB
23 Elfogadva 12ms 13536 KiB
24 Elfogadva 10ms 13376 KiB
subtask4 21/21
25 Elfogadva 469ms 49160 KiB
26 Elfogadva 472ms 49152 KiB
27 Elfogadva 469ms 49160 KiB
28 Elfogadva 469ms 49160 KiB
29 Elfogadva 469ms 49368 KiB
30 Elfogadva 467ms 49384 KiB
subtask5 24/24
31 Elfogadva 6ms 13024 KiB
32 Elfogadva 19ms 15852 KiB
33 Elfogadva 168ms 35828 KiB
34 Elfogadva 301ms 35824 KiB
subtask6 34/34
35 Elfogadva 6ms 11836 KiB
36 Elfogadva 6ms 11968 KiB
37 Elfogadva 6ms 12232 KiB
38 Elfogadva 6ms 12444 KiB
39 Elfogadva 6ms 12660 KiB
40 Elfogadva 6ms 12876 KiB
41 Elfogadva 12ms 13524 KiB
42 Elfogadva 10ms 13380 KiB
43 Elfogadva 12ms 13528 KiB
44 Elfogadva 10ms 13488 KiB
45 Elfogadva 12ms 13532 KiB
46 Elfogadva 10ms 13480 KiB
47 Elfogadva 12ms 13532 KiB
48 Elfogadva 12ms 13528 KiB
49 Elfogadva 12ms 13536 KiB
50 Elfogadva 10ms 13376 KiB
51 Elfogadva 469ms 49160 KiB
52 Elfogadva 472ms 49152 KiB
53 Elfogadva 469ms 49160 KiB
54 Elfogadva 469ms 49160 KiB
55 Elfogadva 469ms 49368 KiB
56 Elfogadva 467ms 49384 KiB
57 Elfogadva 6ms 13024 KiB
58 Elfogadva 19ms 15852 KiB
59 Elfogadva 168ms 35828 KiB
60 Elfogadva 301ms 35824 KiB
61 Elfogadva 321ms 35844 KiB
62 Elfogadva 305ms 34468 KiB
63 Elfogadva 310ms 34872 KiB
64 Elfogadva 310ms 34644 KiB
65 Elfogadva 340ms 36608 KiB
66 Elfogadva 333ms 36404 KiB
67 Elfogadva 342ms 36536 KiB
68 Elfogadva 347ms 36692 KiB
69 Elfogadva 282ms 33488 KiB
70 Elfogadva 342ms 36684 KiB
71 Elfogadva 275ms 33120 KiB
72 Elfogadva 354ms 37300 KiB
73 Elfogadva 349ms 37732 KiB
74 Elfogadva 214ms 37732 KiB
75 Elfogadva 340ms 36520 KiB
76 Elfogadva 338ms 36548 KiB
77 Elfogadva 293ms 34120 KiB