卢俊达

题目大意：

一棵具有n个节点的树，一开始，每个节点上都有一个苹果。现在给出m组动态的操作：(C,i)是摘掉第i个节点上面的苹果(若苹果不存在，则为加上一个苹果)，(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。

思路：

这道题的精髓在于建立树到树状数组的映射关系。首先深搜，确定每个节点所包含子树的范围（即那些节点是其孩子）并对其编号，要求每一课树内的节点拥有连续的编号，这样可以方便利用树状数组特有的sum操作求取连续编号区间（即一棵树）上元素的和。

映射过程：将深搜时各个节点的访问顺序作为其编号。一棵树内的节点总是连续被访问到的。

代码：

#include<stdio.h>
#include<vector>
using namespace std;
vector<int> tree[100001];
//tree[]，邻接表，用于记录节点间的连接关系。 
struct point
//将一棵树的节点用结构体封装。 
{
	int low;
	//low为该节点的编号，亦是其集合（以其为根节点所有子树的集合）的上界。 
	int high;
	//集合的下界。
}range[100001];
int n,m,c[100001];
bool mark[100001];
//标记某一节点上是否有苹果。 
int dfs(int u,int order)
//u为节点，order为访问顺序。 
{
	range[u].low=order;
	int size=tree[u].size();
	for(int i=0;i<size;i++)
		order=dfs(tree[u][i],order+1);
	return range[u].high=order;
	//此时的order是其子树内最后一个被访问到的节点的编号。 
}
int lowbit(int x)
{
	return x&-x;
}
int sum(int end)
//求取编号在区间[1,end]内的节点上的苹果的个数。 
{
	int s=0;
	while(end>0)
	{
		s+=c[end];
		end-=lowbit(end);
	}
	return s;
}
void modify(int pos,int val)
//编号为pos的节点长出或被摘下一个苹果。 
{
	while(pos<=n)
	{
		c[pos]+=val;
		pos+=lowbit(pos);
	}
}
int main()
{
	scanf("%d",&n);
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++)
		mark[i]=true;
	for(int i=0,u,v;i<n-1;i++)
	{
		scanf("%d%d",&u,&v);
		tree[u].push_back(v);
	}
	dfs(1,1);
	for(int i=1;i<=n;i++)
		modify(range[i].low,1);
		//每个节点默认有苹果。 
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		char op;
		int x;
		scanf("\n%c%d",&op,&x);
		if(op=='Q')
			printf("%d\n",sum(range[x].high)-sum(range[x].low-1));
			//以节点x为根的子树的苹果总数即是编号区间[range[x].low-1,range[x].high]内的和。
		else if(mark[range[x].low])
		//该节点有苹果则摘下 
		{
			modify(range[x].low,-1);
			mark[range[x].low]=false;
		}
		//无苹果则长出苹果。 
		else
		{
			modify(range[x].low,1);
			mark[range[x].low]=true;
		}
	}
}