[NTUJ] 0903. Shadow Hunters

題目連結:http://acm.csie.org/ntujudge/problem.php?id=903

---

有趣的好題，想了很久只想的到樹鍊剖分的作法，被雷了才知道更好的做法QQ
對於全子樹加一其實很簡單，就把樹壓扁後把$[in[x], out[x]]$全部加一就好，然後詢問時則單點詢問邊即可。但是另外兩個操作就會變得很難做，所以要用另外一種方式想，考慮一條邊若或被加值，則一定是因為它下面的點有被加值，所以其實對最底下的點加值即可，然後為了怕太上面的人也會被算到，記得超過最頂之後要再減一以免多算，這樣就變成單點加值區間查詢了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
const int N = 100000 + 5;

class BIT1{
	#define lowbit(x) ((x)&(-(x)))
	private:
		int arr[N], size;
		inline int query(int x){
			int r=0;
			while(x){
				r+=arr[x];
				x-=lowbit(x);
			}
			return r;
		}
	public:
		inline void init(int x){
			fill(arr, arr+size, 0);
			size=x;
		}
		inline int query(int l, int r){
			// 1-base (l, r]
			return query(r)-query(l);
		}
		inline void add(int x, int v){
			while(x<size){
				arr[x]+=v;
				x+=lowbit(x);
			}
		}
	#undef lowbit
} bit1;
class BIT2{
	#define lowbit(x) ((x)&(-(x)))
	private:
		int arr[N], size;
		inline void add(int x, int v){
			while(x){
				arr[x]+=v;
				x-=lowbit(x);
			}
		}
	public:
		inline void init(int x){
			fill(arr, arr+size, 0);
			size=x;
		}
		inline void add(int l, int r, int v){
			//1-base (l, r]
			add(l, -v);
			add(r, v);
		}
		inline int query(int x){
			int r=0;
			while(x<size){
				r+=arr[x];
				x+=lowbit(x);
			}
			return r;
		}
	#undef lowbit
} bit2;

int timer;
vector<int> G[N];
int time_in[N], time_out[N];

inline void init(int);
void dfs(int,int);
inline bool anc(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		init(n);
		for(int i=0;i<n-1;i++){
			int u, v; cin>>u>>v;
			G[u].PB(v);
			G[v].PB(u);
		}
		dfs(0, 0);
		int q; cin>>q;
		while(q--){
			char type; cin>>type;
			if(type=='s'){
				int x, y; cin>>x>>y;
				bit1.add(time_in[x], 1);
				bit1.add(time_in[y], -1);
			}else if(type=='h'){
				int x; cin>>x;
				bit2.add(time_in[x]-1, time_out[x]-1, 1);
			}else if(type=='n'){
				int x; cin>>x;
				bit1.add(time_in[x], 1);
			}else if(type=='q'){
				int x, y; cin>>x>>y;
				if(!anc(x, y)) swap(x,y);
				int sm = bit2.query(time_in[x]);
				sm+=bit1.query(time_in[y]-1, time_out[y]-1);
				cout<<sm<<'\n';
			}
		}
	}
	return 0;
}

inline void init(int n){
	for(int i=0;i<n;i++) G[i].clear();
	timer=1;
	bit1.init(n+3);
	bit2.init(n+3);
}

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

inline bool anc(int a, int b){
	return (time_in[a]<=time_in[b])and(time_out[b]<=time_out[a]);
}