POJ 3321 Apple Tree

刷POJ分类的时候遇到的题，只知道是树状数组，但是分支编号不连续，不晓得怎么用树状数组求和。

后来看了解题报告才知道需要把分支通过DFS映射成编号连续的，记录每个子树的起始位置和终止位置，然后再用树状数组求和。

即使明白了思路，代码实现上也还是有很多地方不理解。唉，数据结构学得实在有够糟糕……

树的邻接表表示法每次往表头插入节点也让我费解了好半天Orz……

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 
  5 const int MAXN = 100005;
  6 
  7 struct node    //邻接表保存树
  8 {
  9     int v;
 10     int next;
 11 };
 12 
 13 struct SubTree  //每棵子树的起始点和终止点
 14 {
 15     int st;
 16     int ed;
 17 };
 18 
 19 int N, Q;
 20 int EdgeN, TimeFlag;
 21 node D[MAXN];
 22 SubTree R[MAXN];
 23 int C[MAXN];       //树状数组求和用
 24 int apple[MAXN];   //以u为根的子树上是否有苹果
 25 int head[MAXN];    //以u为根的子树编号为head[u]
 26 
 27 void AddEdge( int u, int v )   //向邻接表中添加一条边
 28 {
 29     D[EdgeN].v = v;
 30     D[EdgeN].next = head[u];
 31     head[u] = EdgeN++;
 32     return;
 33 }
 34 
 35 void DFS( int cur )   //遍历树，给每个分支编号
 36 {
 37     R[cur].st = TimeFlag;     //子树的起始位置
 38     for ( int i = head[cur]; i != -1; i = D[i].next )
 39         DFS( D[i].v );
 40     R[cur].ed = TimeFlag++;   //子树的终止位置
 41     return;
 42 }
 43 
 44 int lowbit( int x )
 45 {
 46     return x & -x;
 47 }
 48 
 49 void Add( int x, int d )  //树状数组更新
 50 {
 51     while ( x <= N )
 52     {
 53         C[x] += d;
 54         x += lowbit(x);
 55     }
 56     return;
 57 }
 58 
 59 int Sum( int x )    //求和
 60 {
 61     int ret = 0;
 62     while ( x > 0 )
 63     {
 64         ret += C[x];
 65         x -= lowbit(x);
 66     }
 67     return ret;
 68 }
 69 
 70 int main()
 71 {
 72     while ( ~scanf( "%d", &N ) )
 73     {
 74         EdgeN = 1;
 75         memset( head, -1, sizeof(head) );
 76         for ( int i = 1; i < N; ++i )
 77         {
 78             int u, v;
 79             scanf( "%d%d", &u, &v );
 80             AddEdge( u, v );
 81         }
 82 
 83         TimeFlag = 1;
 84         DFS( 1 );
 85 
 86         for ( int i = 1; i <= N; ++i )   //初始时整棵树上都有苹果
 87         {
 88             C[i] = lowbit(i);
 89             apple[i] = 1;
 90         }
 91 
 92         scanf( "%d", &Q );
 93         while ( Q-- )
 94         {
 95             char op[4];
 96             int u;
 97             scanf( "%s%d", op, &u );
 98             if ( op[0] == 'C' )
 99             {
100                 int val = 1;
101                 if ( apple[u] ) val = -1;
102                 apple[u] ^= 1;
103                 Add( R[u].ed, val );
104             }
105             else
106                 printf("%d\n", Sum( R[u].ed ) - Sum( R[u].st - 1 ) );
107         }
108     }
109     return 0;
110 }