[Codeforces] 877E. Danil and a Part-time Job

題目連結:http://codeforces.com/problemset/problem/877/E

---

把樹壓扁後題目就轉化成有一個01序列，並且有兩種操作：查詢區間和跟把區間的bit反轉。稍微想一下會發現線段樹可以好好做他，所以就用線段樹維護一下就好了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,bool> PIB;
#define FF first
#define SS second
const int N = 200000 + 5;

class SegTree{
	private:
		PIB nodes[N<<2];
		int n;
		inline int lc(int x){return 2*x+1;}
		inline int rc(int x){return 2*x+2;}
		inline void push(int l, int r, int id){
			if(!nodes[id].SS) return;
			nodes[id].FF = r-l - nodes[id].FF;
			if(r-l > 1){
				nodes[lc(id)].SS ^= nodes[id].SS;
				nodes[rc(id)].SS ^= nodes[id].SS;
			}
			nodes[id].SS = 0;
		}
		inline void pull(int l, int r, int id){
			int val = 0, mid = (l+r)>>1;
			if(nodes[lc(id)].SS) val += mid-l-nodes[lc(id)].FF;
			else val += nodes[lc(id)].FF;
			if(nodes[rc(id)].SS) val += r-mid-nodes[rc(id)].FF;
			else val += nodes[rc(id)].FF;
			nodes[id].FF = val;
		}
		void build(int l, int r, int id, int arr[]){
			nodes[id].SS = 0;
			if(r-l == 1){
				nodes[id].FF = arr[l];
				return;
			}
			int mid = (l+r)>>1;
			build(l, mid, lc(id), arr);
			build(mid, r, rc(id), arr);
			nodes[id].FF = nodes[lc(id)].FF + nodes[rc(id)].FF;
		}
		int query(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return 0;
			push(l, r, id);
			if(ql <= l and r <= qr) return nodes[id].FF;
			int mid = (l+r)>>1;
			return query(ql, qr, l, mid, lc(id))+query(ql, qr, mid, r, rc(id));
		}
		void modify(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return;
			push(l, r, id);
			if(ql <= l and r <= qr){
				nodes[id].SS ^= 1;
				return;
			}
			int mid = (l+r)>>1;
			modify(ql, qr, l, mid, lc(id));
			modify(ql, qr, mid, r, rc(id));
			pull(l, r, id);
		}
	public:
		void build(int size_, int arr[]){
			n = size_;
			build(0, n, 0, arr);
		}
		int query(int l, int r){
			return query(l, r, 0, n, 0);
		}
		void modify(int l, int r){
			modify(l, r, 0, n, 0);
		}
} seg;

vector<int> G[N];
int val[N], arr[N], timer, time_in[N], time_out[N];
void dfs(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=2;i<=n;i++){
		int x; cin>>x;
		G[x].PB(i);
	}
	for(int i=1;i<=n;i++) cin>>val[i];
	dfs(1, 1);
	seg.build(timer, arr);
	int q; cin>>q;
	while(q--){
		string opt; cin>>opt;
		if(opt=="get"){
			int u; cin>>u;
			cout<<seg.query(time_in[u], time_out[u])<<'\n';
		}else{
			int u; cin>>u;
			seg.modify(time_in[u], time_out[u]);
		}
	}
	return 0;
}

void dfs(int w, int f){
	time_in[w] = timer++;
	arr[time_in[w]] = val[w];
	for(auto i: G[w]) dfs(i, w);
	time_out[w] = timer;
}