poj3321.cpp

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 100100

int p = 1;
int indextree[4*MAXN];
bool ck[MAXN];
pair<int, int> number[MAXN];
vector<vector<int> > graph;

//원래 배열의 인덱스 L부터 R까지의 합을 구하는 함수
int find(int L, int R){
	L += p;
	R += p;
	int result = 0;

	while (L <= R){
		if (L & 1){
			result += indextree[L];
			L++;
		}
		if (!(R&1)){
			result += indextree[R];
			R--;
		}
		L >>= 1, R >>= 1;
	}

	return result;
}

//원래 배열의 인덱스 k에 value값을 더해준다.
void update(int k, int value){
	k += p;
	indextree[k] += value;
	for (int i = (k >> 1); i >= 1; i >>= 1)
		indextree[i] = indextree[i * 2] + indextree[i * 2 + 1];
}

//그래프를 dfs탐색하면서 정점에 번호를 매긴다
int now = 0;
void dfs(int vertex){
	now++;
	number[vertex].first = now;

	for (int i = 0; i < graph[vertex].size(); i++){
		if (ck[graph[vertex][i]] == false){
			ck[graph[vertex][i]] = true;
			dfs(graph[vertex][i]);			
		}
	}

	number[vertex].second = now;
}

bool compare(const pair<int, int>& i, const pair<int, int>& j){
	if (i.first == j.second)
		return i.second < j.second;
	return i.first < j.first;
}

int main(){
	int N, temp1, temp2;
	cin >> N;
	//그래프 초기화
	graph.resize(N+1);
	for (int i = 0; i < N - 1; i++){
		scanf("%d%d", &temp1, &temp2);
		graph[temp1].push_back(temp2);
		graph[temp2].push_back(temp1);
	}
	
	ck[1] = true;
	dfs(1);
	
	while (N > p) p <<= 1;
	//인덱스트리 바닥층 초기화
	for (int i = 0; i < N; i++)
		indextree[i + p] = 1;
	for (int i = N + p; i < (p<<1); i++)
		indextree[i] = 0;
	//부모 초기화
	for (int i = p - 1; i >= 1; i--)
		indextree[i] = indextree[i * 2] + indextree[i * 2 + 1];
	
	char m[3];
	int M;
	cin >> M;
	for (int i = 0; i < M; i++){
		scanf("%s", m);
		scanf("%d", &temp1);

		if (m[0] == 'Q')
			printf("%d\n", find(number[temp1].first-1, number[temp1].second-1));
		else{
			if (indextree[p+number[temp1].first-1] == 0)
				update(number[temp1].first-1, 1);
			else
				update(number[temp1].first-1, -1);			
		}
	}

	return 0;
}