10816 2024. 04. 15 18:01:06 Valaki2 Gyors utak cpp17 Elfogadva 100/100 194ms 36088 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6700 KiB
2 Elfogadva 6ms 7972 KiB
subtask2 10/10
3 Elfogadva 4ms 7244 KiB
4 Elfogadva 4ms 7712 KiB
5 Elfogadva 4ms 7796 KiB
6 Elfogadva 4ms 7992 KiB
7 Elfogadva 4ms 8084 KiB
8 Elfogadva 4ms 7992 KiB
subtask3 11/11
9 Elfogadva 4ms 7244 KiB
10 Elfogadva 4ms 7712 KiB
11 Elfogadva 4ms 7796 KiB
12 Elfogadva 4ms 7992 KiB
13 Elfogadva 4ms 8084 KiB
14 Elfogadva 4ms 7992 KiB
15 Elfogadva 7ms 8588 KiB
16 Elfogadva 7ms 8576 KiB
17 Elfogadva 7ms 8696 KiB
18 Elfogadva 7ms 8576 KiB
19 Elfogadva 8ms 8724 KiB
20 Elfogadva 7ms 8788 KiB
21 Elfogadva 8ms 8908 KiB
22 Elfogadva 8ms 8892 KiB
23 Elfogadva 8ms 8956 KiB
24 Elfogadva 7ms 8936 KiB
subtask4 21/21
25 Elfogadva 175ms 35868 KiB
26 Elfogadva 172ms 35876 KiB
27 Elfogadva 172ms 35864 KiB
28 Elfogadva 175ms 35880 KiB
29 Elfogadva 175ms 36088 KiB
30 Elfogadva 171ms 36084 KiB
subtask5 24/24
31 Elfogadva 4ms 8796 KiB
32 Elfogadva 13ms 11252 KiB
33 Elfogadva 98ms 28212 KiB
34 Elfogadva 162ms 28208 KiB
subtask6 34/34
35 Elfogadva 4ms 7244 KiB
36 Elfogadva 4ms 7712 KiB
37 Elfogadva 4ms 7796 KiB
38 Elfogadva 4ms 7992 KiB
39 Elfogadva 4ms 8084 KiB
40 Elfogadva 4ms 7992 KiB
41 Elfogadva 7ms 8588 KiB
42 Elfogadva 7ms 8576 KiB
43 Elfogadva 7ms 8696 KiB
44 Elfogadva 7ms 8576 KiB
45 Elfogadva 8ms 8724 KiB
46 Elfogadva 7ms 8788 KiB
47 Elfogadva 8ms 8908 KiB
48 Elfogadva 8ms 8892 KiB
49 Elfogadva 8ms 8956 KiB
50 Elfogadva 7ms 8936 KiB
51 Elfogadva 175ms 35868 KiB
52 Elfogadva 172ms 35876 KiB
53 Elfogadva 172ms 35864 KiB
54 Elfogadva 175ms 35880 KiB
55 Elfogadva 175ms 36088 KiB
56 Elfogadva 171ms 36084 KiB
57 Elfogadva 4ms 8796 KiB
58 Elfogadva 13ms 11252 KiB
59 Elfogadva 98ms 28212 KiB
60 Elfogadva 162ms 28208 KiB
61 Elfogadva 173ms 28792 KiB
62 Elfogadva 163ms 27760 KiB
63 Elfogadva 166ms 28160 KiB
64 Elfogadva 165ms 28224 KiB
65 Elfogadva 185ms 29460 KiB
66 Elfogadva 180ms 29488 KiB
67 Elfogadva 184ms 29772 KiB
68 Elfogadva 187ms 29844 KiB
69 Elfogadva 148ms 27028 KiB
70 Elfogadva 187ms 30260 KiB
71 Elfogadva 145ms 26640 KiB
72 Elfogadva 193ms 30192 KiB
73 Elfogadva 194ms 30412 KiB
74 Elfogadva 115ms 30448 KiB
75 Elfogadva 179ms 29880 KiB
76 Elfogadva 181ms 29996 KiB
77 Elfogadva 158ms 28308 KiB