POJ 3321 Apple Tree 树状数组

题意：给你一棵n个点，n-1条无向边的树，最初每个节点都是1，然后现在有两种操作，一种是将某个节点的值亦或1，一种是求当前节点及其下属节点的值的和。

方法：转换树状数组。

解析：如何转换树状数组呢？是应用搜索序来转换的。因为树状数组维护的是一个线性的和，而这道题恰巧可以用搜索序来映射到线性，所以采用这种办法。

可以举个例子来说明

如上图所示的树，我们对它进行搜索的时候1是第一个被遍历到的，而只有把所有的点都遍历完事后才会回溯到1，所以可见1的搜索序可以用起始端点以及结束端点即[1,5]来代表，同理，2的起始为2，结束为4，[2,4]来代表2,4就可以用[3,3],5用[4,4],3用[5,5]，这样就把这棵树投影到线性了，再用树状数组就非常简便了。

代码：

#include <stdio.h>
#include <string.h>
struct node
{
    int to ;
    int next ;
};
bool is_used[100001] ;
node edge[100001 * 2] ;
int head[100001] ;
char useless[5] ;
int s[100001] ;
int e[100001] ;
int c[100001] ;
int index ;
int cnt ;
int n ;
void init()
{
    memset(head , -1 , sizeof(head)) ;
    cnt = 1 ;
}
void edgeadd(int from , int to)
{
    edge[cnt].to = to ;
    edge[cnt].next = head[from] ;
    head[from] = cnt++ ;
}
void dfs(int fa , int too)
{
    s[too] = ++index ;
    for(int i = head[too] ; i != -1 ; i = edge[i].next)
    {
        int to = edge[i].to ;
        if(to != fa)
        {
            dfs(too , to) ;
        }
    }
    e[too] = index ;
}
int lowbit(int x)
{
    return x & (-x) ;
}
void updata(int x , int tmp)
{
    while(x <= n)
    {
        c[x] += tmp ;
        x += lowbit(x) ;
    }
}
int getsum(int x)
{
    int sum = 0 ;
    while(x)
    {
        sum += c[x] ;
        x -= lowbit(x) ;
    }
    return sum ;
}
int main()
{
    scanf("%d" , &n) ;
    init() ;
    for(int i = 1 ; i < n ; i++)
    {
        int x , y ;
        scanf("%d%d" , &x , &y) ;
        edgeadd(x , y) ;
        edgeadd(y , x) ;
    }
    dfs(-1 , 1) ;
    for(int i = 1 ; i <= n ; i++)
    {
        updata(i , 1) ;
        is_used[i] = 1 ;
    }
    int q ;
    scanf("%d" , &q) ;
    for(int i = 1 ; i <= q ; i++)
    {
        scanf("%s" , useless) ;
        if(useless[0] == ‘C‘)
        {
            int x ; 
            scanf("%d" , &x) ;
            if(is_used[x] == 1)
            {
                is_used[x] = 0 ; 
                updata(s[x] , -1) ;
            }else
            {
                is_used[x] = 1 ;
                updata(s[x] , 1) ;
            }
        }else
        {
            int x ;
            scanf("%d" , &x) ;
            printf("%d\n" , getsum(e[x]) - getsum(s[x] - 1)) ;
        }
    }
}