/*
 * =====================================================================================
 *
 *       Filename:  3321.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2008-8-15 13:20:06
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Chen Kai (remlostime), remlostime@yahoo.com.cn
 *        Company:  Shanghai University
 *
 * =====================================================================================
 */

#include <iostream>
#include <list>
using namespace std;

list<int> node[100001];
int childNum[100001]; // include itself
int c[100001];
int cSize = 0;
bool canUse[100001];
bool full[100001];
int index2c[100001];
int n;

inline int sum(int index);
void dfs(int index);
inline int lowbit(int x);
inline void add(int index, int delta);

int main()
{
	memset(canUse, true, sizeof(canUse));
	scanf("%d", &n);
	int a, b;
	for(int i = 0; i < n - 1; i++)
	{
		scanf("%d%d", &a, &b);
		node[a].push_back(b);
		node[b].push_back(a);
		canUse[a] = canUse[b] = false;
	}
	memset(canUse, true, sizeof(canUse));
	canUse[1] = false;
	dfs(1);
	/*
	for(int i = 1; i <= n; i++)
		cout << index2c[i] << ' ';
	cout << endl;
	for(int i = 1; i <= n; i++)
		cout << childNum[i] << ' ';
	cout << endl;
	*/
	int m;
	scanf("%d\n", &m);
	char op;
	int index;
	memset(full, true, sizeof(full));
	memset(c, 0, sizeof(c));
	for(int i = 1; i <= n; i++)
		add(i, 1);
	for(int i = 0; i < m; i++)
	{
		scanf("%c%d\n", &op, &index);
		if (op == 'Q')
		{
			int index1 = index2c[index];
			int index2 = index2c[index] - childNum[index];
			printf("%d\n", sum(index1) - sum(index2));
		}
		else
		{
			int index1 = index2c[index];
			full[index] = !full[index];
			if (full[index])
				add(index1, 1);
			else
				add(index1, -1);
		}
	}
	return 0;
}

void dfs(int index)
{
	childNum[index] = 1;
	for(list<int>::iterator iter = node[index].begin(); iter != node[index].end(); iter++)
		if (canUse[*iter])
		{
			canUse[*iter] = false;
			dfs(*iter);
			childNum[index] += childNum[*iter];
		}
	index2c[index] = ++cSize;
}

inline int lowbit(int x)
{
	return x & (-x);
}

inline void add(int index, int delta)
{
	while (index <= n)
	{
		c[index] += delta;
		index += lowbit(index);
	}
}

inline int sum(int index)
{
	int ret = 0;
	while (index)
	{
		ret += c[index];
		index -= lowbit(index);
	}
	return ret;
}

• Re:晕，狂晕～～～～～～～～～～真的比手写的慢很多 这题至少相差800ms (1) remlostime 2008-08-16 16:00:24