POJ 3321-Apple Tree（树状数组）

心已赠人 2022-07-26 08:46 200阅读 0赞

# Apple Tree #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 23729</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 7132</td> 
  </tr> 
 </tbody> 
</table>

Description

There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.

The tree has *N* forks which are connected by branches. Kaka numbers the forks by 1 to*N* and the root is always numbered by 1. Apples will grow on the forks and two apple won't grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.

The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?

![3321_1.gif][]

Input

The first line contains an integer *N* (*N* ≤ 100,000) , which is the number of the forks in the tree.  
The following *N* \- 1 lines each contain two integers *u* and *v*, which means fork*u* and fork*v* are connected by a branch.  
The next line contains an integer *M* (*M* ≤ 100,000).  
The following *M* lines each contain a message which is either  
"**C *x***" which means the existence of the apple on fork  *x* has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.  
or  
"**Q *x***" which means an inquiry for the number of apples in the sub-tree above the fork*x*, including the apple (if exists) on the fork x  
Note the tree is full of apples at the beginning

Output

For every inquiry, output the correspond answer per line.

Sample Input

3
    1 2
    1 3
    3
    Q 1
    C 2
    Q 1

Sample Output

3
    2

Source

[POJ Monthly--2007.08.05][], Huang, Jinsong  
  
题目意思：  
是有一棵果树，书上有n个分叉点，从1~n给各个分叉点编号。苹果长在分叉点的地方，一个分叉点最多只能长一个苹果。求这棵树上一共有多少个苹果。  
最开始的时候树上长满苹果，即每个分叉点都有一个苹果。  
  
先输入n，表示分叉点个数；再输入u，v两个分叉点表示这两个点由树枝连在一起；  
C x，表示x点得苹果状态发生变化：若以前有，则吃掉变无；若以前没有，则长出一个苹果。  
Q x，表示查询x点这棵子树上的苹果数目。  
  
用树状数组，方便统计子树的权值和。  
  
![Center][]这个是下面程序中sum函数所求的值。

#include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const int maxn=100000+2;
    struct node1
    {
        int next,tail;//第i条边相连的节点是edge[i].tail
        //连接的下一条边的序号是edge[i].next
    } edge[maxn];//边表
    struct node2
    {//以节点i为根的子树在后根序列中的区间为(apple[i].l,apple[i].r)
        int r,l;
    } apple[maxn];//苹果树
    int s[maxn];//s[i]是节点i相连的第i条边
    int c[maxn];//c树状数组
    int a[maxn];//a[i]是后根遍历中第i个节点的权值
    int cnt;//后根遍历序号
    void DFS(int u)//初始u=1
    {//从节点u出发，计算每个节点为根的子树区间(apple[].l,apple[].r)
        int i;
        apple[u].l=cnt;
        for(i=s[u]; i!=-1; i=edge[i].next)
            DFS(edge[i].tail);
        apple[u].r=cnt++;
    }
    int lowbit(int x)//计算二进制数x右方的第一位1对应的权
    {
        return x&(-x);
    }
    void change(int x)//从a[x]开始调整一棵子树
    {
        int i;
        if(a[x])//有苹果，都加一
            for(i=x; i<cnt; i+=lowbit(i))
                c[i]++;
        else//苹果被吃掉了
            for(i=x; i<cnt; i+=lowbit(i))
                c[i]--;
    }
    int sum(int x)//计算节点x上的苹果总数
    {
        int i,res=0;
        for(i=x; i>0; i-=lowbit(i))
            res+=c[i];
        return res;
    }
    int main()
    {
        int i,m,n,t1,t2,t;
        char str[3];
        scanf("%d",&n);//树的节点数
        memset(s,-1,sizeof(s[0])*(n+1));
        memset(c,0,sizeof(c[0])*(n+1));
        memset(apple,0,sizeof(apple[0])*(n+1));
        for(i=0; i<n-1; ++i)
        {
            scanf("%d%d",&t1,&t2);//读第i条边(t1,t2)
            edge[i].tail=t2;//第i条边连接t2
            edge[i].next=s[t1];//其后继指针指向t1连接的上一条边
            s[t1]=i;//节点t1相连的边序号i
        }
        cnt=1;
        DFS(1);//节点1开始DFS，计算每个节点的在后根遍历的顺序值，节点权值设为1
        for(i=1; i<=n; ++i)
        {
            a[i]=1;//长满苹果
            change(i);//构造树状数组c
        }
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s%d",str,&t);//命令标志、节点序号
            if(str[0]=='Q')//输出节点上的苹果树
                printf("%d\n",sum(apple[t].r)-sum(apple[t].l-1));
            else
            {//计算节点上的变化情况
                a[apple[t].r]=(a[apple[t].r]+1)%2;//有无苹果的转换
                change(apple[t].r);//更新这棵子树
            }
        }
        return 0;
    }

[3321_1.gif]: /images/20220724/4a4f02b16a214fde82d29b1071629cf7.png
[POJ Monthly--2007.08.05]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.08.05
[Center]: /images/20220724/5ed743b6336449618f33efe34193ff81.png