#include<cstdio>
using namespace std;

const int N=100001,INF=2000000000;
struct edge
{
	int v,next;
}e[N<<1];
int n,head[N],c[N],pos[N],end[N],id;
bool vis[N];
char s[101];

int min(int a,int b)
{
	if(a<b)return a;
	return b;
}

void add(int x,int v)
{
	while(x<=n)
	{
		c[x]+=v;
		x+=x&-x;
	}
}

void dfs(int u)
{
	vis[u]=true;
	int i,v;
	for(i=head[u];i;i=e[i].next)
	{
		v=e[i].v;
		if(!vis[v])
		{
			dfs(v);
			end[u]=min(end[u],end[v]);
		}
	}
	id++;
	add(id,1);
	pos[u]=id;
	end[u]=min(end[u],id);
}

int sum(int x)
{
	int res=0;
	while(x)
	{
		res+=c[x];
		x-=x&-x;
	}
	return res;
}

int main()
{
	int m,i,tot=0,u,v,x;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		tot++;
		e[tot].v=v;
		e[tot].next=head[u];
		head[u]=tot;
		tot++;
		e[tot].v=u;
		e[tot].next=head[v];
		head[v]=tot;
		end[i]=INF;
	}
	end[n]=INF;
	dfs(1);
	scanf("%d",&m);
	while(m)
	{
		scanf("%s%d",s,&x);
		if(s[0]=='Q')printf("%d\n",sum(pos[x])-sum(end[x]-1));
		else
		{
			if(vis[x])add(pos[x],-1);
			else add(pos[x],1);
			vis[x]=!vis[x];
		}
		m--;
	}
	return 0;
}

• Re:树状数组 5272K 391MS (1342) 1093824239 2019-01-18 09:44:34