维护子树和。dfs序就搞定。树剖用不上。
记得,取反时标记取反而不是打上!
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int sze[maxn],dfn[maxn],rev[maxn];
int xds[maxn<<2],tag[maxn<<2];
int a[maxn];
int n,m;
vector<int> e[maxn];
void dfs(int u,int f){
dfn[u]=++dfn[0];
rev[dfn[0]]=u;
sze[u]=1;
for(auto x:e[u]){
if(x!=f){
dfs(x,u);
sze[u]+=sze[x];
}
}
}
void pushup(int k){
xds[k]=xds[k<<1]+xds[k<<1|1];
}
void flip(int k,int l,int r){
xds[k]=(r-l+1)-xds[k];
tag[k]^=1;
}
void build(int k,int l,int r){
tag[k]=0;
if(l==r){
xds[k]=a[rev[l]];
return ;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void pushdown(int k,int l,int r){
int mid=l+r>>1;
if(tag[k]){
flip(k<<1,l,mid);
flip(k<<1|1,mid+1,r);
tag[k]=0;
pushup(k);
}
}
void modify(int k,int l,int r,int x,int y){
//cout<<"modify"<<xds[k]<<" "<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<tag[k]<<endl;
if(x<=l&&r<=y)return flip(k,l,r);
int mid=l+r>>1;
pushdown(k,l,r);
if(x<=mid)modify(k<<1,l,mid,x,y);
if(mid<y)modify(k<<1|1,mid+1,r,x,y);
pushup(k);
}
int query(int k,int l,int r,int x,int y){
// cout<<xds[k]<<" "<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<tag[k]<<endl;
if(x<=l&&r<=y)return xds[k];
int mid=l+r>>1;int res=0;
pushdown(k,l,r);
if(x<=mid)res+=query(k<<1,l,mid,x,y);
if(mid<y)res+=query(k<<1|1,mid+1,r,x,y);
return res;
}
int main(){
cin>>n;
for(int i=2;i<=n;i++){
int x;
cin>>x;
e[x].push_back(i);
e[i].push_back(x);
}
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
dfs(1,0);
build(1,1,n);
for(int i=1;i<=m;i++){
string f;int x;
cin>>f>>x;
if(f[0]=='g')cout<<query(1,1,n,dfn[x],dfn[x]+sze[x]-1)<<endl;
else modify(1,1,n,dfn[x],dfn[x]+sze[x]-1);
}
return 0;
}