poj 3321

题意：问某个节点的子节点以及它自己总共有多少个苹果，每C一次的话，则代表如果这个节点有苹果，则把苹果拿下，如果没有，则添加上去

思路：这个思路确实我没有想到过，用dfs从新建立一个新的序列，然后对这个新的序列求和（线段树和树状数组都可以）

关于DFS建立一个新的序列是这样的

就是从根节点开始dfs，用一个结构题记录这个节点是从哪个节点开始进入的（它本身的序列），以及最后的一个子节点是哪个节点

这样的话，就相当与构成了一个序列，就是从l->r就是它的编号，也正是因为这样，所以可以用树状数组来做

不理解可以把树构造出来，然后自己在列一下就会清楚

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #define maxn 200008
  5 using namespace std;
  6 
  7 int n, pos, q,k;
  8 int head[maxn];
  9 int tree[maxn];
 10 
 11 struct T {
 12     int l, r;
 13 }num[maxn];
 14 
 15 struct Node {
 16     int u, to;
 17 }node[maxn];
 18 
 19 void addedge(int u, int v)
 20 {
 21     node[pos].u = v;
 22     node[pos].to = head[u];
 23     head[u] = pos++;
 24 }
 25 
 26 void add(int x, int num)
 27 {
 28     while (x <= n)
 29     {
 30         tree[x] += num;
 31         x += x&-x;
 32     }
 33 }
 34 
 35 int read(int x)
 36 {
 37     int sum = 0;
 38     while (x)
 39     {
 40         sum += tree[x];
 41         x -= x&-x;
 42     }
 43     return sum;
 44 }
 45 
 46 void dfs(int root)
 47 {
 48     num[root].l = k;
 49     for (int i = head[root]; i != -1; i = node[i].to)
 50         k++,dfs(node[i].u);
 51     num[root].r = k;
 52 }
 53 
 54 int main()
 55 {
 56    // freopen("in.txt","r",stdin);
 57     bool vis[maxn];
 58     int u, v;
 59     char tmp;
 60     k = 1;
 61     pos = 1;
 62     memset(head,-1,sizeof(head));
 63     memset(vis,false,sizeof(vis));
 64     scanf("%d", &n);
 65     for(int i = 1;i<n;i++)
 66     {
 67         scanf("%d%d", &u, &v);
 68         addedge(u, v);
 69     }
 70     dfs(1);
 71     scanf("%d",&u);
 72     for(int i = 1;i<=n;i++)
 73     {
 74         vis[i] = true;
 75         add(i,1);
 76     }
 77     getchar();
 78     while(u--)
 79     {
 80         scanf("%c%d",&tmp,&v);
 81         if(tmp=='Q')
 82         {
 83             printf("%d
",read(num[v].r)-read(num[v].l-1));
 84         }else {
 85             if(vis[v])
 86             {
 87                 vis[v] = false;
 88                 add(num[v].l,-1);
 89             }
 90             else
 91             {
 92                  vis[v] = true;
 93                  add(num[v].l,1);
 94             }
 95 
 96         }
 97         getchar();
 98     }
 99     return 0;
100 }