POJ 3321 Apple Tree（树状数组）

浏览数：20 / 时间：2015年06月11日

题意：大概是说一颗树有n个分岔，然后给你n-1对关系，标明分岔u和分岔v是有边连着的，然后给你两个指令，让你在Q出现的时候按照要求输出。

思路：典型的树状数组。但是因为没有弄好数组，所以要用DFS先映射一下，好吧我承认我说不下去了，六级没过，CF又掉了100多分，脑子完全不转转了。。。。。。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 500004 ;
int head[maxn],start[maxn] ,num[maxn],data[maxn];
int m,n,cnt ,cntt;
bool vis[maxn] ;

struct node
{
    int l,r ;
    int next ;
}Node[maxn] ;

void addegde(int u,int v)
{
    Node[cnt].l = u ;
    Node[cnt].r = v ;
    Node[cnt].next = head[u] ;
    head[u] = cnt++ ;
}

void dfs(int u)
{
    start[u] = ++ cntt ;
    vis[u] = true ;
    for(int i = head[u] ; i+1 ; i = Node[i].next)
    {
        int v = Node[i].r ;
        if(!vis[v])
        dfs(v) ;
    }
    num[u] = cntt ;
}
int lowbit(int x)
{
    return x&(-x) ;
}
int sum(int i )
{
    int summ = 0 ;
    while(i > 0)
    {
        summ += data[i] ;
        i -= lowbit(i) ;
    }
    return summ ;
}

void update(int i,int val)
{
    while(i <= n)
    {
        data[i] += val ;
        i += lowbit(i) ;
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        cnt = cntt = 0 ;
        memset(head,-1,sizeof(head)) ;
        memset(num,0,sizeof(num)) ;
        memset(start,0,sizeof(start)) ;
        memset(data,0,sizeof(data)) ;
        memset(vis,false,sizeof(vis)) ;
        int x,y ;
        for(int i = 1 ; i <= n-1 ; i++ )
        {
            scanf("%d %d",&x,&y) ;
            addegde(x,y) ;
        }
        dfs(1) ;
        for(int i = 1 ; i <= n ; i++)
            update(i,1) ;
        scanf("%d",&m) ;
        getchar() ;
        for(int j = 1 ; j <= m ; j++)
        {
            char ch ;
            scanf("%c",&ch) ;
            if(ch == ‘Q‘)
            {
                scanf("%d",&x) ;
                printf("%d\n",sum(num[x])-sum(start[x]-1)) ;
            }
            else if(ch == ‘C‘)
            {
                scanf("%d",&x) ;
                if(sum(start[x])-sum(start[x]-1))
                    update(start[x],-1) ;
                else
                    update(start[x],1) ;
            }
            getchar() ;
        }
    }
    return 0;
}