codeforces 877-E

题目链接：codeforces 877-E

题目大意：一棵树上，有些灯亮着，有些灯暗的，我们每次可以查询某个节点的亮灯个数，或者改变某个子树的暗亮情况（暗变成亮，亮变成暗）。

比较简单的dfs序，然后用线段树区间亮的个数即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,q,cnt,st[N],ed[N],a[N];
int head[N],nex[N],to[N],tot;
struct node{
	int l,r,sum,lazy;
}t[N<<2];
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x){
	st[x]=++cnt;
	for(int i=head[x];i;i=nex[i])	dfs(to[i]);
	ed[x]=cnt;
}
inline void push_up(int p){
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
inline void push_down(int p){
	if(t[p].lazy){
		t[p<<1].lazy^=1;	t[p<<1|1].lazy^=1;
		t[p<<1].sum=(t[p<<1].r-t[p<<1].l+1-t[p<<1].sum);
		t[p<<1|1].sum=(t[p<<1|1].r-t[p<<1|1].l+1-t[p<<1|1].sum);
		t[p].lazy=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l;	t[p].r=r;
	if(l==r)	return ;	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void updata(int p,int x){
	if(t[p].l==t[p].r){
		t[p].sum=1;	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	updata(p<<1,x);
	else	updata(p<<1|1,x);
	push_up(p);
}
void change(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r){
		t[p].lazy^=1;	t[p].sum=(r-l+1-t[p].sum);	return ;
	}
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r);
	else if(l>mid)	change(p<<1|1,l,r);
	else	change(p<<1,l,mid),change(p<<1|1,mid+1,r);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].sum;
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return ask(p<<1,l,mid)+ask(p<<1|1,mid+1,r);
}
signed main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		int x;	scanf("%d",&x);	add(x,i);
	}
	dfs(1);	build(1,1,n);
	for(int i=1;i<=n;i++){
		int x;	scanf("%d",&x);	if(x)	updata(1,st[i]);
	}
	scanf("%d",&q);	char op[5];	int x; 
	while(q--){
		scanf("%s %d",op,&x);
		if(op[0]=='g')	printf("%d\n",ask(1,st[x],ed[x]));
		else	change(1,st[x],ed[x]);
	}
	return 0;
}