171812025-05-29 12:06:04AblablablaGyors utakcpp17Runtime error 0/1001ms576 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(){
    auto abc = ifstream("be2.txt");

    ll n, q;
    abc >> n >> q;

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

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

        csucsok[a].push_back(i);
    }
    cout << "beolvas kesz\n";

    dfs(0);
    cout << "dfs kesz\n";

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

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

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

        cout << i << " kesz\n";
    }

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

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

    while(q--){
        ll a;
        abc >> 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error1ms316 KiB
2Runtime error1ms316 KiB
subtask20/10
3Runtime error1ms576 KiB
4Runtime error1ms316 KiB
5Runtime error1ms316 KiB
6Runtime error1ms316 KiB
7Runtime error1ms500 KiB
8Runtime error1ms316 KiB
subtask30/11
9Runtime error1ms576 KiB
10Runtime error1ms316 KiB
11Runtime error1ms316 KiB
12Runtime error1ms316 KiB
13Runtime error1ms500 KiB
14Runtime error1ms316 KiB
15Runtime error1ms316 KiB
16Runtime error1ms316 KiB
17Runtime error1ms316 KiB
18Runtime error1ms316 KiB
19Runtime error1ms496 KiB
20Runtime error1ms508 KiB
21Runtime error1ms316 KiB
22Runtime error1ms316 KiB
23Runtime error1ms564 KiB
24Runtime error1ms500 KiB
subtask40/21
25Runtime error1ms316 KiB
26Runtime error1ms316 KiB
27Runtime error1ms332 KiB
28Runtime error1ms316 KiB
29Runtime error1ms512 KiB
30Runtime error1ms496 KiB
subtask50/24
31Runtime error1ms316 KiB
32Runtime error1ms316 KiB
33Runtime error1ms316 KiB
34Runtime error1ms508 KiB
subtask60/34
35Runtime error1ms576 KiB
36Runtime error1ms316 KiB
37Runtime error1ms316 KiB
38Runtime error1ms316 KiB
39Runtime error1ms500 KiB
40Runtime error1ms316 KiB
41Runtime error1ms316 KiB
42Runtime error1ms316 KiB
43Runtime error1ms316 KiB
44Runtime error1ms316 KiB
45Runtime error1ms496 KiB
46Runtime error1ms508 KiB
47Runtime error1ms316 KiB
48Runtime error1ms316 KiB
49Runtime error1ms564 KiB
50Runtime error1ms500 KiB
51Runtime error1ms316 KiB
52Runtime error1ms316 KiB
53Runtime error1ms332 KiB
54Runtime error1ms316 KiB
55Runtime error1ms512 KiB
56Runtime error1ms496 KiB
57Runtime error1ms316 KiB
58Runtime error1ms316 KiB
59Runtime error1ms316 KiB
60Runtime error1ms508 KiB
61Runtime error1ms316 KiB
62Runtime error1ms316 KiB
63Runtime error1ms508 KiB
64Runtime error1ms316 KiB
65Runtime error1ms512 KiB
66Runtime error1ms512 KiB
67Runtime error1ms316 KiB
68Runtime error1ms316 KiB
69Runtime error1ms316 KiB
70Runtime error1ms316 KiB
71Runtime error1ms316 KiB
72Runtime error1ms316 KiB
73Runtime error1ms512 KiB
74Runtime error1ms316 KiB
75Runtime error1ms316 KiB
76Runtime error1ms316 KiB
77Runtime error1ms508 KiB