[POJ][3321][树状数组] Apple Tree

题目大意：

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

思路：

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

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

代码：

#include
#include
using namespace std;
vector 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;i0)
    {
        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;
        }
    }
}