108162024-04-15 18:01:06Valaki2Gyors utakcpp17Accepted 100/100194ms36088 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1e5 + 7;

int n, q;
int par[1 + maxn];
vector<int> graph[1 + maxn];
int val[1 + maxn];
int dist[1 + maxn];
int in[1 + maxn];
int ending[1 + maxn];
int timer;

int tree[1 + 4 * maxn];
int lazy[1 + 4 * maxn];

void build(int v, int vl, int vr) {
    if(vl == vr) {
        tree[v] = dist[vl];
    } else {
        int mid = (vl + vr) / 2;
        build(2 * v, vl, mid);
        build(2 * v + 1, mid + 1, vr);
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

void prop(int v, int vl, int vr) {
    if(lazy[v] != 0) {
        if(vl != vr) {
            lazy[2 * v] ^= 1;
            lazy[2 * v + 1] ^= 1;
        }
        tree[v] = (vr - vl + 1) - tree[v];
        lazy[v] = 0;
    }
}

void update(int v, int vl, int vr, int ul, int ur) {
    //cout << v << " " << vl << " " << vr << "\n";
    prop(v, vl, vr);
    if(ul > vr || ur < vl) {
        return;
    }
    if(vl == ul && vr == ur) {
        lazy[v] ^= 1;
        prop(v, vl, vr);
        return;
    }
    prop(v, vl, vr);
    int mid = (vl + vr) / 2;
    update(2 * v, vl, mid, ul, min(ur, mid));
    update(2 * v + 1, mid + 1, vr, max(ul, mid + 1), ur);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

void dfs_euler(int cur) {
    timer++;
    in[cur] = timer;
    for(int nei : graph[cur]) {
        dfs_euler(nei);
    }
    ending[cur] = timer;
}

void solve() {
    cin >> n >> q;
    for(int i = 2; i <= n; i++) {
        cin >> par[i];
        graph[par[i]].pb(i);
    }
    dfs_euler(1);
    for(int i = 2; i <= n; i++) {
        cin >> val[i];
        dist[in[i]] = dist[in[par[i]]] ^ val[i];
    }
    build(1, 1, n);
    /*for(int i = 1; i <= n; i++) {
        cout << dist[i] << " " << ending[i] << "\n";
    }*/
    for(int qi = 0; qi <= q; qi++) {
        if(qi != 0) {
            int change;
            cin >> change;
            change++;
            // upd
            update(1, 1, n, in[change], ending[change]);
            //cout << in[change] << " " << ending[change] << "\n";
        }
        int ans = 0;
        int even_cnt = tree[1];
        //cout << "-----\n";
        int odd_cnt = n - even_cnt;
        ans += even_cnt * (even_cnt - 1) / 2;
        ans += odd_cnt * (odd_cnt - 1) / 2;
        cout << ans << " ";
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms6700 KiB
2Accepted6ms7972 KiB
subtask210/10
3Accepted4ms7244 KiB
4Accepted4ms7712 KiB
5Accepted4ms7796 KiB
6Accepted4ms7992 KiB
7Accepted4ms8084 KiB
8Accepted4ms7992 KiB
subtask311/11
9Accepted4ms7244 KiB
10Accepted4ms7712 KiB
11Accepted4ms7796 KiB
12Accepted4ms7992 KiB
13Accepted4ms8084 KiB
14Accepted4ms7992 KiB
15Accepted7ms8588 KiB
16Accepted7ms8576 KiB
17Accepted7ms8696 KiB
18Accepted7ms8576 KiB
19Accepted8ms8724 KiB
20Accepted7ms8788 KiB
21Accepted8ms8908 KiB
22Accepted8ms8892 KiB
23Accepted8ms8956 KiB
24Accepted7ms8936 KiB
subtask421/21
25Accepted175ms35868 KiB
26Accepted172ms35876 KiB
27Accepted172ms35864 KiB
28Accepted175ms35880 KiB
29Accepted175ms36088 KiB
30Accepted171ms36084 KiB
subtask524/24
31Accepted4ms8796 KiB
32Accepted13ms11252 KiB
33Accepted98ms28212 KiB
34Accepted162ms28208 KiB
subtask634/34
35Accepted4ms7244 KiB
36Accepted4ms7712 KiB
37Accepted4ms7796 KiB
38Accepted4ms7992 KiB
39Accepted4ms8084 KiB
40Accepted4ms7992 KiB
41Accepted7ms8588 KiB
42Accepted7ms8576 KiB
43Accepted7ms8696 KiB
44Accepted7ms8576 KiB
45Accepted8ms8724 KiB
46Accepted7ms8788 KiB
47Accepted8ms8908 KiB
48Accepted8ms8892 KiB
49Accepted8ms8956 KiB
50Accepted7ms8936 KiB
51Accepted175ms35868 KiB
52Accepted172ms35876 KiB
53Accepted172ms35864 KiB
54Accepted175ms35880 KiB
55Accepted175ms36088 KiB
56Accepted171ms36084 KiB
57Accepted4ms8796 KiB
58Accepted13ms11252 KiB
59Accepted98ms28212 KiB
60Accepted162ms28208 KiB
61Accepted173ms28792 KiB
62Accepted163ms27760 KiB
63Accepted166ms28160 KiB
64Accepted165ms28224 KiB
65Accepted185ms29460 KiB
66Accepted180ms29488 KiB
67Accepted184ms29772 KiB
68Accepted187ms29844 KiB
69Accepted148ms27028 KiB
70Accepted187ms30260 KiB
71Accepted145ms26640 KiB
72Accepted193ms30192 KiB
73Accepted194ms30412 KiB
74Accepted115ms30448 KiB
75Accepted179ms29880 KiB
76Accepted181ms29996 KiB
77Accepted158ms28308 KiB