171822025-05-29 12:07:24AblablablaGyors utakcpp17Elfogadva 100/100342ms18856 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> csucsok;
vector<ll> tin, tout;
ll ido;

void dfs(ll akt){
    tin[akt] = ido;
    ido++;

    for(ll x : csucsok[akt]){
        dfs(x);
    }

    tout[akt] = ido;
    ido++;
}

struct segTree{
    ll meret = 1;
    vector<ll> fa;
    vector<bool> csere;

    void meretez(ll n){
        while(meret < n){
            meret *= 2;
        }

        fa.assign(2*meret - 1, 0);
        csere.assign(2*meret - 1, 0);
    }

    ll keres(ll a, ll b, ll ind, ll kezd, ll veg){
        if(veg < kezd){
            return 0;
        }
        if(veg < a || b < kezd){
            return 0;
        } else if(kezd <= a && b <= veg){
            return fa[ind];
        }

        ll k = (a + b) / 2;

        ll akt = keres(a, k, 2*ind +1, kezd, veg) + keres(k + 1, b, 2*ind + 2, kezd, veg);

        if(csere[ind]){
            akt = (b - a + 1) - akt;
        }

        return akt;
    }

    ll valt(ll a, ll b, ll ind, ll kezd, ll veg){
        if(veg < a || b < kezd){
            return fa[ind];
        } else if(kezd <= a && b <= veg){
            fa[ind] = (b - a + 1) - fa[ind];
            csere[ind] = !csere[ind];
            return fa[ind];
        }

        ll k = (a + b) / 2;

        fa[ind] = valt(a, k, 2*ind + 1, kezd, veg) + valt(k + 1, b, 2*ind + 2, kezd, veg);

        if(csere[ind]){
            fa[ind] = (b - a + 1) - fa[ind];
        }

        return fa[ind];
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, q;
    cin >> n >> q;

    csucsok.assign(n, vector<ll>());
    tin.assign(n, 0);
    tout.assign(n, 0);

    for(ll i = 1; i < n; i++){
        ll a;
        cin >> a;
        a--;

        csucsok[a].push_back(i);
    }

    dfs(0);

    segTree fa;
    fa.meretez(2*n);

    for(ll i = 1; i < n; i++){
        ll a;
        cin >> a;

        if(a){
            fa.valt(0, fa.meret - 1, 0, tin[i], tout[i]);
        }

    }

    ll ps = fa.fa[0]/2;
    ll pt = n - ps;

    cout << (ps*(ps - 1) + pt*(pt - 1))/2 << " ";

    while(q--){
        ll a;
        cin >> a;

        fa.valt(0, fa.meret - 1, 0, tin[a], tout[a]);

        ps = fa.fa[0]/2;
        pt = n - ps;
        cout << (ps*(ps - 1) + pt*(pt - 1))/2 << " ";
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva4ms824 KiB
subtask210/10
3Elfogadva1ms420 KiB
4Elfogadva2ms532 KiB
5Elfogadva1ms588 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms508 KiB
8Elfogadva1ms316 KiB
subtask311/11
9Elfogadva1ms420 KiB
10Elfogadva2ms532 KiB
11Elfogadva1ms588 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms508 KiB
14Elfogadva1ms316 KiB
15Elfogadva4ms696 KiB
16Elfogadva4ms644 KiB
17Elfogadva6ms568 KiB
18Elfogadva4ms564 KiB
19Elfogadva4ms656 KiB
20Elfogadva4ms548 KiB
21Elfogadva4ms692 KiB
22Elfogadva6ms772 KiB
23Elfogadva4ms564 KiB
24Elfogadva4ms568 KiB
subtask421/21
25Elfogadva310ms18856 KiB
26Elfogadva305ms18704 KiB
27Elfogadva342ms18832 KiB
28Elfogadva273ms18832 KiB
29Elfogadva335ms18740 KiB
30Elfogadva333ms18740 KiB
subtask524/24
31Elfogadva1ms500 KiB
32Elfogadva14ms1588 KiB
33Elfogadva104ms12340 KiB
34Elfogadva248ms14132 KiB
subtask634/34
35Elfogadva1ms420 KiB
36Elfogadva2ms532 KiB
37Elfogadva1ms588 KiB
38Elfogadva1ms316 KiB
39Elfogadva1ms508 KiB
40Elfogadva1ms316 KiB
41Elfogadva4ms696 KiB
42Elfogadva4ms644 KiB
43Elfogadva6ms568 KiB
44Elfogadva4ms564 KiB
45Elfogadva4ms656 KiB
46Elfogadva4ms548 KiB
47Elfogadva4ms692 KiB
48Elfogadva6ms772 KiB
49Elfogadva4ms564 KiB
50Elfogadva4ms568 KiB
51Elfogadva310ms18856 KiB
52Elfogadva305ms18704 KiB
53Elfogadva342ms18832 KiB
54Elfogadva273ms18832 KiB
55Elfogadva335ms18740 KiB
56Elfogadva333ms18740 KiB
57Elfogadva1ms500 KiB
58Elfogadva14ms1588 KiB
59Elfogadva104ms12340 KiB
60Elfogadva248ms14132 KiB
61Elfogadva230ms14388 KiB
62Elfogadva204ms13876 KiB
63Elfogadva216ms13972 KiB
64Elfogadva228ms13804 KiB
65Elfogadva237ms14700 KiB
66Elfogadva231ms14680 KiB
67Elfogadva279ms14640 KiB
68Elfogadva275ms14644 KiB
69Elfogadva197ms13288 KiB
70Elfogadva252ms14736 KiB
71Elfogadva209ms12992 KiB
72Elfogadva264ms14900 KiB
73Elfogadva238ms14904 KiB
74Elfogadva158ms13260 KiB
75Elfogadva272ms14552 KiB
76Elfogadva263ms14644 KiB
77Elfogadva204ms13620 KiB