108162024-04-15 18:01:06Valaki2Gyors utakcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6700 KiB
2Elfogadva6ms7972 KiB
subtask210/10
3Elfogadva4ms7244 KiB
4Elfogadva4ms7712 KiB
5Elfogadva4ms7796 KiB
6Elfogadva4ms7992 KiB
7Elfogadva4ms8084 KiB
8Elfogadva4ms7992 KiB
subtask311/11
9Elfogadva4ms7244 KiB
10Elfogadva4ms7712 KiB
11Elfogadva4ms7796 KiB
12Elfogadva4ms7992 KiB
13Elfogadva4ms8084 KiB
14Elfogadva4ms7992 KiB
15Elfogadva7ms8588 KiB
16Elfogadva7ms8576 KiB
17Elfogadva7ms8696 KiB
18Elfogadva7ms8576 KiB
19Elfogadva8ms8724 KiB
20Elfogadva7ms8788 KiB
21Elfogadva8ms8908 KiB
22Elfogadva8ms8892 KiB
23Elfogadva8ms8956 KiB
24Elfogadva7ms8936 KiB
subtask421/21
25Elfogadva175ms35868 KiB
26Elfogadva172ms35876 KiB
27Elfogadva172ms35864 KiB
28Elfogadva175ms35880 KiB
29Elfogadva175ms36088 KiB
30Elfogadva171ms36084 KiB
subtask524/24
31Elfogadva4ms8796 KiB
32Elfogadva13ms11252 KiB
33Elfogadva98ms28212 KiB
34Elfogadva162ms28208 KiB
subtask634/34
35Elfogadva4ms7244 KiB
36Elfogadva4ms7712 KiB
37Elfogadva4ms7796 KiB
38Elfogadva4ms7992 KiB
39Elfogadva4ms8084 KiB
40Elfogadva4ms7992 KiB
41Elfogadva7ms8588 KiB
42Elfogadva7ms8576 KiB
43Elfogadva7ms8696 KiB
44Elfogadva7ms8576 KiB
45Elfogadva8ms8724 KiB
46Elfogadva7ms8788 KiB
47Elfogadva8ms8908 KiB
48Elfogadva8ms8892 KiB
49Elfogadva8ms8956 KiB
50Elfogadva7ms8936 KiB
51Elfogadva175ms35868 KiB
52Elfogadva172ms35876 KiB
53Elfogadva172ms35864 KiB
54Elfogadva175ms35880 KiB
55Elfogadva175ms36088 KiB
56Elfogadva171ms36084 KiB
57Elfogadva4ms8796 KiB
58Elfogadva13ms11252 KiB
59Elfogadva98ms28212 KiB
60Elfogadva162ms28208 KiB
61Elfogadva173ms28792 KiB
62Elfogadva163ms27760 KiB
63Elfogadva166ms28160 KiB
64Elfogadva165ms28224 KiB
65Elfogadva185ms29460 KiB
66Elfogadva180ms29488 KiB
67Elfogadva184ms29772 KiB
68Elfogadva187ms29844 KiB
69Elfogadva148ms27028 KiB
70Elfogadva187ms30260 KiB
71Elfogadva145ms26640 KiB
72Elfogadva193ms30192 KiB
73Elfogadva194ms30412 KiB
74Elfogadva115ms30448 KiB
75Elfogadva179ms29880 KiB
76Elfogadva181ms29996 KiB
77Elfogadva158ms28308 KiB