[TIOJ] 1272. The Agency

題目連結:http://tioj.infor.org/problems/1272

---

給定一棵樹，然後要求詢問某個節點的值是偶數或奇數，或者對一整顆子樹加一。不妨把樹壓平後，透過進入時間戳與出去的時間戳，得到一個區間$[in[x], out[x])$，而其實這個區間就是x的子樹，所以發現要對子樹加值就是對那個區間加值，而查詢則是查$in[x]$。把問題轉成單點查詢區間加值後，其實一個BIT就可以做到了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back

const int N = 100000 + 5;

class BIT{
	private:
		int arr[N], size=0;
		inline int lowbit(int x){
			return x&-x;
		}
	public:
		void init(int s){
			fill(arr, arr+s, 0);
			size=s;
		}
		//1-base (l, r]
		void add(int l, int r, int v){
			add(l, -v);
			add(r, v);
		}
		void add(int s, int v){
			while(s){
				arr[s]+=v;
				s-=lowbit(s);
			}
		}
		int query(int x){
			int r=0;
			while(x<size){
				r+=arr[x];
				x+=lowbit(x);
			}
			return r;
		}
} bit;

vector<int> G[N];
int step=1, in[N], out[N];
void dfs(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m; cin>>n>>m;
	for(int i=1;i<=n;++i){
		int s; cin>>s;
		while(s--){
			int x; cin>>x;
			G[i].PB(x);
		}
	}
	dfs(1);
	bit.init(step+3);
	while(m--){
		bool type;int who;
		cin>>type>>who;
		if(type)
			cout<<(bit.query(in[who])&1)<<'\n';
		else
			bit.add(in[who]-1, out[who]-1, 1);
	}
	return 0;
}

void dfs(int x){
	in[x]=step++;
	for(auto i:G[x]) dfs(i);
	out[x]=step;
}