109332024-04-20 15:56:34k_balintGyors utakcpp17Elfogadva 100/100207ms41476 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=2e5+5;

int tree[4*c][2], lazy[4*c];

int n,q,tt;
vector<int> adj[c];
int tin[c],tout[c],arr[c], mp[c];

void dfs(int v, int p){
    arr[v]^=arr[p];
    tin[v]=tout[v]=++tt;
    mp[tin[v]]=v;
    for(int x:adj[v]){
        if(x != p){
            dfs(x,v);
            tout[v]=tout[x];
        }
    }
}

void build(int v, int l, int r){
    if(l==r){
        int x=mp[l];
        tree[v][arr[x]]=1;
        return;
    }
    int mid=l+r>>1;
    build(2*v,l,mid);
    build(2*v+1,mid+1,r);
    tree[v][0]=tree[2*v][0]+tree[2*v+1][0];
    tree[v][1]=tree[2*v][1]+tree[2*v+1][1];
}

void push(int v, int l, int r){
    if(lazy[v]==0) return;
    swap(tree[v][0],tree[v][1]);
    if(l!=r){
        lazy[2*v]^=1;
        lazy[2*v+1]^=1;
    }
    lazy[v]=0;
}

void update(int v, int l, int r, int x, int y){
    push(v,l,r);
    if(l>r || l>y || x>r || x>y) return;
    if(x<=l && r<=y){
        swap(tree[v][0], tree[v][1]);
        if(l!=r){
            lazy[2*v]^=1;
            lazy[2*v+1]^=1;
        }
        return;
    }
    int mid=l+r>>1;
    update(2*v,l,mid,x,y);
    update(2*v+1,mid+1,r,x,y);
    tree[v][0]=tree[2*v][0]+tree[2*v+1][0];
    tree[v][1]=tree[2*v][1]+tree[2*v+1][1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    tt=0;
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        int a; cin>>a;
        adj[a].push_back(i);
        adj[i].push_back(a);
    }

    for(int i=2;i<=n;i++) cin>>arr[i];

    dfs(1,0);
    build(1,1,n);
    
    cout << 1ll*tree[1][0]*(tree[1][0]-1)/2 + 1ll*tree[1][1]*(tree[1][1]-1)/2 << ' ';
    while(q--){
        int x; cin>>x;
        ++x;
        update(1,1,n,tin[x],tout[x]);
        cout << 1ll*tree[1][0]*(tree[1][0]-1)/2 + 1ll*tree[1][1]*(tree[1][1]-1)/2 << ' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva6ms11344 KiB
2Elfogadva8ms12460 KiB
subtask210/10
3Elfogadva6ms12148 KiB
4Elfogadva6ms11896 KiB
5Elfogadva6ms12108 KiB
6Elfogadva6ms12116 KiB
7Elfogadva6ms12300 KiB
8Elfogadva6ms12256 KiB
subtask311/11
9Elfogadva6ms12148 KiB
10Elfogadva6ms11896 KiB
11Elfogadva6ms12108 KiB
12Elfogadva6ms12116 KiB
13Elfogadva6ms12300 KiB
14Elfogadva6ms12256 KiB
15Elfogadva8ms12992 KiB
16Elfogadva8ms12992 KiB
17Elfogadva8ms13048 KiB
18Elfogadva8ms13056 KiB
19Elfogadva8ms12992 KiB
20Elfogadva8ms13256 KiB
21Elfogadva9ms13236 KiB
22Elfogadva9ms13464 KiB
23Elfogadva9ms13544 KiB
24Elfogadva9ms13464 KiB
subtask421/21
25Elfogadva187ms41060 KiB
26Elfogadva187ms40940 KiB
27Elfogadva189ms41028 KiB
28Elfogadva193ms41228 KiB
29Elfogadva187ms41336 KiB
30Elfogadva187ms41476 KiB
subtask524/24
31Elfogadva7ms13388 KiB
32Elfogadva14ms15352 KiB
33Elfogadva108ms29108 KiB
34Elfogadva180ms29200 KiB
subtask634/34
35Elfogadva6ms12148 KiB
36Elfogadva6ms11896 KiB
37Elfogadva6ms12108 KiB
38Elfogadva6ms12116 KiB
39Elfogadva6ms12300 KiB
40Elfogadva6ms12256 KiB
41Elfogadva8ms12992 KiB
42Elfogadva8ms12992 KiB
43Elfogadva8ms13048 KiB
44Elfogadva8ms13056 KiB
45Elfogadva8ms12992 KiB
46Elfogadva8ms13256 KiB
47Elfogadva9ms13236 KiB
48Elfogadva9ms13464 KiB
49Elfogadva9ms13544 KiB
50Elfogadva9ms13464 KiB
51Elfogadva187ms41060 KiB
52Elfogadva187ms40940 KiB
53Elfogadva189ms41028 KiB
54Elfogadva193ms41228 KiB
55Elfogadva187ms41336 KiB
56Elfogadva187ms41476 KiB
57Elfogadva7ms13388 KiB
58Elfogadva14ms15352 KiB
59Elfogadva108ms29108 KiB
60Elfogadva180ms29200 KiB
61Elfogadva184ms29432 KiB
62Elfogadva180ms30244 KiB
63Elfogadva186ms30032 KiB
64Elfogadva181ms30084 KiB
65Elfogadva192ms29496 KiB
66Elfogadva188ms29512 KiB
67Elfogadva194ms29540 KiB
68Elfogadva202ms29564 KiB
69Elfogadva165ms29272 KiB
70Elfogadva197ms29640 KiB
71Elfogadva157ms29064 KiB
72Elfogadva200ms30108 KiB
73Elfogadva207ms30624 KiB
74Elfogadva127ms30628 KiB
75Elfogadva192ms29484 KiB
76Elfogadva193ms29492 KiB
77Elfogadva178ms30516 KiB