#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<fstream>
#include<algorithm>
using namespace std;
int C[100101];
int b[100101];
int e[100101];
vector<int>N[100101];
bool flag[100101]={0};
inline int Lowbit(int x)
{
	return x&(x^(x-1));
}
inline int sum(int p)
{
	int result=0;
	while(p>0){
		result+=C[p];
		p-=Lowbit(p);
	}
	return result;
}
inline void Modify(int p,int n,int v)
{
	while(p<=n){
		C[p]+=v;
		p+=Lowbit(p);
	}
}
int num;
void tree(int p)
{
	num++;
	b[p]=num;
	for(int i=0;i<N[p].size();i++){
		if(b[N[p][i]]>0)continue;
		tree(N[p][i]);
	}
	e[p]=num;
}
int main()
{
	int n,i,j,a,b1;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d %d",&a,&b1);
		N[a].push_back(b1);
		N[b1].push_back(a);
	}
	tree(1);
	int m;char s[10];
	scanf("%d",&m);
	for(i=0;i<m;i++){
		scanf("%s %d",s,&a);
		if(s[0]=='Q'){
			int s=e[a]-b[a]+1+sum(e[a])-sum(b[a]-1);
			/*int sum=e[a]-b[a]+1;
			int p=e[a];
			while(p>0){
				sum+=C[p];
				p-=p&(p^(p-1));
			}
			p=b[a]-1;
			while(p>0){
				sum-=C[p];
				p-=p&(p^(p-1));
			}*/
			printf("%d\n",s);
		}
		else{
			if(flag[a]==0)j=-1;
			else j=1;
			Modify(b[a],n,j);
			/*int p=b[a];
			while(p<=n){
				C[p]+=j;
				p+=p&(p^(p-1));
			}*/

			flag[a]=!flag[a];
		}
	}



	return 0;
}







	

		

• Re:用树状树组做怎么还超时 (16) qiaokan 2008-06-14 19:08:24
  • Re:用树状树组做怎么还超时 (32) zhxiaot 2008-06-15 16:14:54
    • Re:用树状树组做怎么还超时 (34) zhxiaot 2008-06-15 16:34:14