109332024-04-20 15:56:34k_balintGyors utakcpp17Accepted 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 << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted6ms11344 KiB
2Accepted8ms12460 KiB
subtask210/10
3Accepted6ms12148 KiB
4Accepted6ms11896 KiB
5Accepted6ms12108 KiB
6Accepted6ms12116 KiB
7Accepted6ms12300 KiB
8Accepted6ms12256 KiB
subtask311/11
9Accepted6ms12148 KiB
10Accepted6ms11896 KiB
11Accepted6ms12108 KiB
12Accepted6ms12116 KiB
13Accepted6ms12300 KiB
14Accepted6ms12256 KiB
15Accepted8ms12992 KiB
16Accepted8ms12992 KiB
17Accepted8ms13048 KiB
18Accepted8ms13056 KiB
19Accepted8ms12992 KiB
20Accepted8ms13256 KiB
21Accepted9ms13236 KiB
22Accepted9ms13464 KiB
23Accepted9ms13544 KiB
24Accepted9ms13464 KiB
subtask421/21
25Accepted187ms41060 KiB
26Accepted187ms40940 KiB
27Accepted189ms41028 KiB
28Accepted193ms41228 KiB
29Accepted187ms41336 KiB
30Accepted187ms41476 KiB
subtask524/24
31Accepted7ms13388 KiB
32Accepted14ms15352 KiB
33Accepted108ms29108 KiB
34Accepted180ms29200 KiB
subtask634/34
35Accepted6ms12148 KiB
36Accepted6ms11896 KiB
37Accepted6ms12108 KiB
38Accepted6ms12116 KiB
39Accepted6ms12300 KiB
40Accepted6ms12256 KiB
41Accepted8ms12992 KiB
42Accepted8ms12992 KiB
43Accepted8ms13048 KiB
44Accepted8ms13056 KiB
45Accepted8ms12992 KiB
46Accepted8ms13256 KiB
47Accepted9ms13236 KiB
48Accepted9ms13464 KiB
49Accepted9ms13544 KiB
50Accepted9ms13464 KiB
51Accepted187ms41060 KiB
52Accepted187ms40940 KiB
53Accepted189ms41028 KiB
54Accepted193ms41228 KiB
55Accepted187ms41336 KiB
56Accepted187ms41476 KiB
57Accepted7ms13388 KiB
58Accepted14ms15352 KiB
59Accepted108ms29108 KiB
60Accepted180ms29200 KiB
61Accepted184ms29432 KiB
62Accepted180ms30244 KiB
63Accepted186ms30032 KiB
64Accepted181ms30084 KiB
65Accepted192ms29496 KiB
66Accepted188ms29512 KiB
67Accepted194ms29540 KiB
68Accepted202ms29564 KiB
69Accepted165ms29272 KiB
70Accepted197ms29640 KiB
71Accepted157ms29064 KiB
72Accepted200ms30108 KiB
73Accepted207ms30624 KiB
74Accepted127ms30628 KiB
75Accepted192ms29484 KiB
76Accepted193ms29492 KiB
77Accepted178ms30516 KiB