#include "circuit.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;
int N,M;
const int MOD=1e9+2022;
vector<vector<int>> child;
vector<int> p;
vector<int> aP;
vector<int> apR;
vector<int> a;
//SUM
struct node {
node* left;
node* right;
int sum=0;
int sumoff=0;
int lazy=0;
void update(){
sum=left->sum+right->sum;
sumoff=left->sumoff+right->sumoff;
}
};
struct segtree {
int n;
node* root=new node{nullptr,nullptr,0,0,0};
void propagate(node* x){
if(x->lazy%2){
if(x->left!=NULL) {
swap(x->left->sum,x->left->sumoff);
x->left->lazy++;
}
if(x->right!=NULL) {
swap(x->right->sum,x->right->sumoff);
x->right->lazy++;
}
x->lazy++;
}
}
void update(node* x, int l, int r, int qL, int qR){
if(l>qR||r<qL) return;
if(l>=qL&&r<=qR){
x->lazy++;
swap(x->sum,x->sumoff);
return;
}
propagate(x);
int mid=(l+r)/2;
update(x->left,l,mid,qL,qR);
update(x->right,mid+1,r,qL,qR);
x->update();
}
void build(node* x, int l, int r){
if(l==r){
x->sum=apR[l+N]*a[l+N];
x->sumoff=apR[l+N]*(1-a[l+N]);
return;
}
int mid=(l+r)/2;
x->left=new node{nullptr,nullptr,0,0,0};
x->right=new node{nullptr,nullptr,0,0,0};
build(x->left,l,mid);
build(x->right,mid+1,r);
x->update();
}
void update(int l, int r){
update(root,0,n-1,l,r);
}
int query(){
return root->sum;
}
void build(int x){
n=x;
build(root,0,n-1);
}
};
int setup_ap(int x){
if(x>=N) return aP[x]=1;
aP[x]=1;
for (auto u : child[x]) aP[x]=(aP[x]*setup_ap(u))%MOD;
aP[x]=(aP[x]*sz(child[x]))%MOD;
return (aP[x])%MOD;
}
void setup_apr(int x, int c){
vector<int> rgt(sz(child[x])+1,1);
for (int j=sz(child[x])-1; j>=0; j--) {
rgt[j]=(rgt[j+1]*aP[child[x][j]])%MOD;
}
int mP=1;
apR[x]=c;
for (int j=0; j<sz(child[x]); j++) {
int u=child[x][j];
int v=(rgt[j+1]*mP)%MOD;
setup_apr(u,(c*v)%MOD);
mP=(mP*aP[u])%MOD;
}
return;
}
segtree seg;
void init(signed n, signed m, std::vector<signed> P, std::vector<signed> A) {
N=n; M=m;
p.resize(N+M);
aP.resize(N+M);
apR.resize(N+M);
for (int i = 0; i < N+M; i++) p[i]=P[i];
child.resize(N+M); a.resize(N+M);
for (int i = 1; i < N+M; i++) child[P[i]].push_back(i);
for (int i = N; i < N+M; i++) a[i] = A[i-N];
setup_ap(0);
setup_apr(0,1);
seg.build(M);
}
signed count_ways(signed L, signed R) {
seg.update(L-N,R-N);
int sum=seg.query();
return (int)(sum);
}
