107132024-04-10 10:01:44szilGyors utakcpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted6ms11596 KiB
2Accepted9ms12944 KiB
subtask210/10
3Accepted6ms11836 KiB
4Accepted6ms11968 KiB
5Accepted6ms12232 KiB
6Accepted6ms12444 KiB
7Accepted6ms12660 KiB
8Accepted6ms12876 KiB
subtask311/11
9Accepted6ms11836 KiB
10Accepted6ms11968 KiB
11Accepted6ms12232 KiB
12Accepted6ms12444 KiB
13Accepted6ms12660 KiB
14Accepted6ms12876 KiB
15Accepted12ms13524 KiB
16Accepted10ms13380 KiB
17Accepted12ms13528 KiB
18Accepted10ms13488 KiB
19Accepted12ms13532 KiB
20Accepted10ms13480 KiB
21Accepted12ms13532 KiB
22Accepted12ms13528 KiB
23Accepted12ms13536 KiB
24Accepted10ms13376 KiB
subtask421/21
25Accepted469ms49160 KiB
26Accepted472ms49152 KiB
27Accepted469ms49160 KiB
28Accepted469ms49160 KiB
29Accepted469ms49368 KiB
30Accepted467ms49384 KiB
subtask524/24
31Accepted6ms13024 KiB
32Accepted19ms15852 KiB
33Accepted168ms35828 KiB
34Accepted301ms35824 KiB
subtask634/34
35Accepted6ms11836 KiB
36Accepted6ms11968 KiB
37Accepted6ms12232 KiB
38Accepted6ms12444 KiB
39Accepted6ms12660 KiB
40Accepted6ms12876 KiB
41Accepted12ms13524 KiB
42Accepted10ms13380 KiB
43Accepted12ms13528 KiB
44Accepted10ms13488 KiB
45Accepted12ms13532 KiB
46Accepted10ms13480 KiB
47Accepted12ms13532 KiB
48Accepted12ms13528 KiB
49Accepted12ms13536 KiB
50Accepted10ms13376 KiB
51Accepted469ms49160 KiB
52Accepted472ms49152 KiB
53Accepted469ms49160 KiB
54Accepted469ms49160 KiB
55Accepted469ms49368 KiB
56Accepted467ms49384 KiB
57Accepted6ms13024 KiB
58Accepted19ms15852 KiB
59Accepted168ms35828 KiB
60Accepted301ms35824 KiB
61Accepted321ms35844 KiB
62Accepted305ms34468 KiB
63Accepted310ms34872 KiB
64Accepted310ms34644 KiB
65Accepted340ms36608 KiB
66Accepted333ms36404 KiB
67Accepted342ms36536 KiB
68Accepted347ms36692 KiB
69Accepted282ms33488 KiB
70Accepted342ms36684 KiB
71Accepted275ms33120 KiB
72Accepted354ms37300 KiB
73Accepted349ms37732 KiB
74Accepted214ms37732 KiB
75Accepted340ms36520 KiB
76Accepted338ms36548 KiB
77Accepted293ms34120 KiB