codeforces 877 F. Ann and Books（dfs序維護線段樹）

http://codeforces.com/contest/877/problem/F

題意：現有一棵樹，每個節點上有0或1，現有2種操作

1.将子樹每個節點值取反

2.查詢子樹節點為1的數量

思路：樹上問題考慮，dfs序維護線段樹，首先讓節點儲存亮燈的個數，那麼每次取反即為區間長度減去亮燈數，每次更新時打上标記，1表示子區間翻轉，0表示不翻轉，每次x^1即可

pushdown操作時，讓子區間根據長度取反

每次更新前pushdown，更新完pushup

查詢前pushdown

#include<bits/stdc++.h>
#define fi first
#define se second
#define log2(a) log(n)/log(2)
#define show(a) cout<<a<<endl;
#define show2(a,b) cout<<a<<" "<<b<<endl;
#define show3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl;
#define tim printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
using namespace std;
 
typedef long long ll;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<P, ll> LP;
const ll inf = 1e18;
const int N = 2e6 + 10;
const ll mod = 1e9+7;
const int base = 131;
const double pi = acos ( -1 );
const double eps = 1e-8;
inline ll mul(ll x,ll y) { return (x*y-(ll)((long double)x*y/mod)*mod+mod)%mod;}
inline ll ksm(ll a,ll b) {ll ans=1;while(b){if(b&1)ans=mul(ans,a);a=mul(a,a),b>>=1;}return ans;}
 
#define a(i,j) a[(i-1)*m+(j)]
#define b(i,j) b[(i-1)*m+(j)]
 
unordered_map<ll, ll> mp;
 
 
ll n, m,x,y,z,k,a[N],b[N],c[N];
ll ans,t,flag;
ll num[N],vis[N];
vector<ll> v[N];
ll sum,cnt;
ll in[N],out[N];
ll tree[N];
int lazy[N];
char s[N];
 
void dfs(int x,int fa)
{
	in[x]=++cnt;
	num[cnt]=x;
	for(int to:v[x])
	{
		if(to==fa) continue;
		dfs(to,x);
	}
	out[x]=cnt;
}
void push_down(ll l,ll r,ll rt)
{
	int mid=l+r >> 1;
	tree[rt<<1]=mid-l+1-tree[rt<<1];
	tree[rt<<1|1]=r-mid-tree[rt<<1|1];
	lazy[rt<<1]^=1;
	lazy[rt<<1|1]^=1;
	lazy[rt]=0;
}
 
void build(int l,int r,int rt)
{
	if(l==r)
	{
		//show3("rt ",l,num[l])
		tree[rt]=a[num[l]];
		return ;
	}
	int mid=l+r >> 1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
 
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
 
void update(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		//show3(rt,r,l)
		tree[rt]=r-l+1-tree[rt];
		lazy[rt]^=1;
		return ;
	}
	if(lazy[rt]) push_down(l,r,rt);
	int mid=l+r >> 1;
	if(L<=mid) update(L,R,l,mid,rt<<1);
	if(R>mid) update(L,R,mid+1,r,rt<<1|1);
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
 
ll query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		return tree[rt];
	}
	ll ans=0;
	if(lazy[rt]) push_down(l,r,rt);
	int mid=l+r>>1;
	if(L<=mid) ans+=query(L,R,l,mid,rt<<1);
	if(R>mid) ans+=query(L,R,mid+1,r,rt<<1|1);
	return ans;
}
int main()
{
 
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	cin>>n;
	for(ll i=2;i<=n;i++)
	{
		cin>>x;
		v[x].push_back(i);
		v[i].push_back(x);
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1,0);
	build(1,n,1);
	cin>>t;
	while(t--)
	{
		cin>>s>>x;
		if(s[0]=='p')
		{
			update(in[x],out[x],1,n,1);
		}
		else
		{
			cout<<query(in[x],out[x],1,n,1)<<endl;
		}
	}
 
}