107132024-04-10 10:01:44szilGyors utakcpp17Elfogadva 100/100472ms49384 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva6ms11596 KiB
2Elfogadva9ms12944 KiB
subtask210/10
3Elfogadva6ms11836 KiB
4Elfogadva6ms11968 KiB
5Elfogadva6ms12232 KiB
6Elfogadva6ms12444 KiB
7Elfogadva6ms12660 KiB
8Elfogadva6ms12876 KiB
subtask311/11
9Elfogadva6ms11836 KiB
10Elfogadva6ms11968 KiB
11Elfogadva6ms12232 KiB
12Elfogadva6ms12444 KiB
13Elfogadva6ms12660 KiB
14Elfogadva6ms12876 KiB
15Elfogadva12ms13524 KiB
16Elfogadva10ms13380 KiB
17Elfogadva12ms13528 KiB
18Elfogadva10ms13488 KiB
19Elfogadva12ms13532 KiB
20Elfogadva10ms13480 KiB
21Elfogadva12ms13532 KiB
22Elfogadva12ms13528 KiB
23Elfogadva12ms13536 KiB
24Elfogadva10ms13376 KiB
subtask421/21
25Elfogadva469ms49160 KiB
26Elfogadva472ms49152 KiB
27Elfogadva469ms49160 KiB
28Elfogadva469ms49160 KiB
29Elfogadva469ms49368 KiB
30Elfogadva467ms49384 KiB
subtask524/24
31Elfogadva6ms13024 KiB
32Elfogadva19ms15852 KiB
33Elfogadva168ms35828 KiB
34Elfogadva301ms35824 KiB
subtask634/34
35Elfogadva6ms11836 KiB
36Elfogadva6ms11968 KiB
37Elfogadva6ms12232 KiB
38Elfogadva6ms12444 KiB
39Elfogadva6ms12660 KiB
40Elfogadva6ms12876 KiB
41Elfogadva12ms13524 KiB
42Elfogadva10ms13380 KiB
43Elfogadva12ms13528 KiB
44Elfogadva10ms13488 KiB
45Elfogadva12ms13532 KiB
46Elfogadva10ms13480 KiB
47Elfogadva12ms13532 KiB
48Elfogadva12ms13528 KiB
49Elfogadva12ms13536 KiB
50Elfogadva10ms13376 KiB
51Elfogadva469ms49160 KiB
52Elfogadva472ms49152 KiB
53Elfogadva469ms49160 KiB
54Elfogadva469ms49160 KiB
55Elfogadva469ms49368 KiB
56Elfogadva467ms49384 KiB
57Elfogadva6ms13024 KiB
58Elfogadva19ms15852 KiB
59Elfogadva168ms35828 KiB
60Elfogadva301ms35824 KiB
61Elfogadva321ms35844 KiB
62Elfogadva305ms34468 KiB
63Elfogadva310ms34872 KiB
64Elfogadva310ms34644 KiB
65Elfogadva340ms36608 KiB
66Elfogadva333ms36404 KiB
67Elfogadva342ms36536 KiB
68Elfogadva347ms36692 KiB
69Elfogadva282ms33488 KiB
70Elfogadva342ms36684 KiB
71Elfogadva275ms33120 KiB
72Elfogadva354ms37300 KiB
73Elfogadva349ms37732 KiB
74Elfogadva214ms37732 KiB
75Elfogadva340ms36520 KiB
76Elfogadva338ms36548 KiB
77Elfogadva293ms34120 KiB