poj 3321 Apple Tree（树状数组）

题意：一颗有n个分支的苹果树，根为1，每个分支只有一个苹果，给出n-1个分支的关系和给出m个操作，Q x表示询问x的子树（包括x）苹果的数量，C x表示若分支x上有苹果，则摘下来，若没有则会生出一个，输出每个询问的值。

分析：每个分支其实就是一个节点，先dfs整个树，求出每个节点的时间戳，即每个节点第一次访问的时间和最后一次访问的时间，分别用begin和end记录，以时间戳为编号，则在begin[x]和end[x]之间的编号的节点就是x的子树，以时间戳为树状数组的下标，查询时，只要求第一次访问的编号到最后一次访问的编号之间的和就行了，即sum(end[x])-sum(begin[x]-1)；修改时，只要修改第一次访问的编号即可，即update(begin[x])。但是修改前要判断该位置是0或1，0则加1,1则减1。

还有别忘了初始化。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 100010
 4 struct EDGE{
 5     int v,next;
 6 }edge[N];
 7 int c[N],first[N],begin[N],end[N];
 8 int n,g,count;
 9 void AddEdge(int u,int v)
10 {
11     edge[g].v=v;
12     edge[g].next=first[u];
13     first[u]=g++;
14 }
15 int lowbit(int x)
16 {
17     return x&(-x);
18 }
19 void update(int x,int num)
20 {
21     while(x<=n)
22     {
23         c[x]+=num;
24         x+=lowbit(x);
25     }
26 }
27 int sum(int x)
28 {
29     int s=0;
30     while(x>0)
31     {
32         s+=c[x];
33         x-=lowbit(x);
34     }
35     return s;
36 }
37 void dfs(int u)
38 {
39     int i;
40     begin[u]=++count;
41     for(i=first[u];i!=-1;i=edge[i].next)
42         dfs(edge[i].v);
43     end[u]=count;
44 }
45 int main()
46 {
47     int u,v,m,ans,i;
48     char s[10];
49     scanf("%d",&n);
50     g=0;
51     memset(first,-1,sizeof(first));
52     for(i=0;i<n-1;i++)
53     {
54         scanf("%d%d",&u,&v);
55         AddEdge(u,v);
56     }
57     count=0;
58     dfs(1);
59     for(i=1;i<=n;i++)
60         update(i,1);
61     scanf("%d",&m);
62     while(m--)
63     {
64         scanf("%s",s);
65         if(s[0]=='Q')
66         {
67             scanf("%d",&u);
68             ans=sum(end[u])-sum(begin[u]-1);
69             printf("%d
",ans);
70         }
71         else
72         {
73             scanf("%d",&u);
74             if(sum(begin[u])-sum(begin[u]-1))
75                 update(begin[u],-1);
76             else
77                 update(begin[u],1);
78         }
79     }
80     return 0;
81 }

View Code