学步园

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

思路：

树状数组。这道题重点怎么建立树到树状数组的映射关系：利用dfs遍历树，对每个节点进行两次编号，第一次搜到第i个节点时的深度dep，为这个节点管辖区间的上限low[i](也为这个节点的下标)，然后搜这个节点的子节点，最后搜回来后的深度dep，为这个节点管辖区间的下限high[i]，如下图所示。接下来就是树状数组部分了。

//4860K  
 454MS

#include <stdio.h>
#include <string.h>
#define M 100010
#define lowbit(x) (x&(-x))
int head[M],low[M],high[M],vis[M],mark[M];
int ar[M];
int n,p,dep;
struct data
{
    int
to,next;
}edge[M];

void dfs (int
u)          
//这个映射方法太巧妙了，学习了
{
    low[u] =
++dep;      
//第一次的深度
    vis[u] =
1;
    for (int i =
head[u];i != -1;i = edge[i].next)
       
while (!vis[edge[i].to])
           
dfs (edge[i].to);
    high[u] =
dep;      
//返回的深度
}
void addedge (int cu,int cv)
{
    edge[p].to =
cv;
    edge[p].next
= head[cu];
    head[cu] = p
++;
}

void add (int u,int w)
{
    while (u
<= n)
    {
       
ar[u] += w;
       
u += lowbit(u);
    }
}

int sum (int u)
{
    int ans =
0;
    while (u
> 0)
    {
       
ans += ar[u];
       
u -= lowbit(u);
    }
    return
ans;
}
int main ()
{
    int
i,m,u,v,root;
    char
op;
    while
(~scanf ("%d",&n))
    {
       
p = 0;
       
dep = 0;
       
memset (head,-1,sizeof(head));
       
memset (ar,0,sizeof(ar));
       
memset (vis,0,sizeof(vis));

       
for (i = 1;i <= n;i ++)
       
{
           
mark[i] =
1;       
//1表示有苹果
           
add(i,1);
       
}
       
for (i = 1;i < n;i ++)
       
{
           
scanf ("%d %d",&u,&v);