bzoj1103: [POI2007]大都市meg

利用dfs序的性质，使用树状数组统计

记录一下每个点进入dfs和退出dfs的时间，将进入的权值赋为1，退出的赋为-1,。每次修改公路，就把这两个值都修改为0，输出前缀和

const int N = 2500010;
struct Edge {
	int V;
	Edge *Next;
	
	Edge() {}
	Edge(int _V, Edge *_Next) : V(_V), Next(_Next) {}
} *First[N];
int n, m;
int In[N], Out[N], Tot, Count[N << 1];

inline void Input() {
	scanf("%d", &n);
	rep(i, 1, n) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(x > y) swap(x, y);
		First[x] = new Edge(y, First[x]);
	}
}

#define lowbit(x) ((x) & (-(x)))

inline void Change(int V, int Val) {
	for( ; V <= Tot; V += lowbit(V)) Count[V] += Val;
}

inline int Ask(int V) {
	int Ret = 0;
	for(; V > 0; V -= lowbit(V)) Ret += Count[V];
	return Ret;
}

#undef lowbit

inline void Init() {
	static stack<int> Stack;
	static bool Vis[N];
	Stack.push(1);
	while(sz(Stack)) {
		int x = Stack.top();
		
		if(!Vis[x]) In[x] = ++Tot, Vis[x] = 1;
		
		Edge *Tab = First[x];
		if(Tab != NULL) {
			Stack.push(Tab->V);
			First[x] = First[x]->Next;
		} else Stack.pop(), Out[x] = ++Tot;
	}
	
	For(i, 2, n) Change(In[i], 1), Change(Out[i], -1);
}

inline void Solve() {
	Init();
	
	for(scanf("%d", &m); (n - 1 + (m--)); ) {
		char Opt = ' ';
		int x, y;
		
		while(!let(Opt)) Opt = getchar();
		if(Opt == 'W') scanf("%d", &x), printf("%d\n", Ask(In[x]));
		else {
			scanf("%d%d", &x, &y);
			if(x > y) swap(x, y);
			Change(In[y], -1), Change(Out[y], 1);
		}
	}
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1103");
	#endif
	Input();
	Solve();
	return 0;
}