poj 3321 Apple Tree(一维树状数组)

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

题意：

苹果树上n个分叉，Q是询问，C是改变状态。。。。

开始的处理比较难，参考了一下大神的思路，构图成邻接表并用DFS编号

白书上一维树状数组模板：

 1 void add(int x,int d)
 2 {
 3     while(x <= n)
 4     {
 5         c[x] += d;
 6         x +=lowbit(x);
 7     }
 8 }
 9 int sum(int x)
10 {
11     int ret = 0;
12     while(x > 0)
13     {
14         ret += c[x];
15         x -= lowbit(x);
16     }
17     return ret;
18 }

AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 using namespace std;
  7 const int maxn = 100010;
  8 int s[maxn],e[maxn],c[maxn],num;
  9 int head[maxn],n,cnt;
 10 bool vis[maxn];
 11 struct node
 12 {
 13     int v,next;
 14 }g[maxn];
 15 
 16 void init()
 17 {
 18     int i;
 19     memset(head,-1,sizeof(head));
 20     cnt = 0; num = 0;
 21     for(i=0; i<=n; i++)
 22     {
 23         c[i] = 0;
 24         vis[i] = false;
 25     }
 26 }
 27 void add_e(int u,int v)
 28 {
 29     g[cnt].v = v;
 30     g[cnt].next = head[u];
 31     head[u] = cnt++;
 32 }
 33 int lowbit(int x)
 34 {
 35     return x&(-x);
 36 }
 37 
 38 void add(int x,int d)
 39 {
 40     while(x <= n)
 41     {
 42         c[x] += d;
 43         x +=lowbit(x);
 44     }
 45 }
 46 int sum(int x)
 47 {
 48     int ret = 0;
 49     while(x > 0)
 50     {
 51         ret += c[x];
 52         x -= lowbit(x);
 53     }
 54     return ret;
 55 }
 56 void dfs(int pos)
 57 {
 58     s[pos] = ++num;
 59     for (int i = head[pos]; i != -1; i = g[i].next)
 60     {
 61         int v = g[i].v;
 62         dfs(v);
 63     }
 64     e[pos] = num;
 65 }
 66 
 67 int main()
 68 {
 69     int x,y,i,q;
 70     char op[5];
 71     scanf("%d",&n);
 72     init();
 73     for(i = 0; i < n-1; i++)
 74     {
 75         cin>>x>>y;
 76         add_e(x,y); //邻接表构图
 77     }
 78     dfs(1); //编号
 79     for (i = 1; i <= n; i++)
 80     add(i,1);
 81     cin>>q;
 82     while (q--)
 83     {
 84         cin>>op>>x;
 85         if (op[0] == ‘Q‘)
 86             printf("%d\n",sum(e[x]) - sum(s[x] - 1));  //输出连续的和
 87         else       //改变状态
 88         {
 89             if (!vis[x])
 90             {
 91                 add(s[x],-1); 
 92                 vis[x] = true;
 93             }
 94             else
 95             {
 96                 add(s[x],1);
 97                 vis[x] = false;
 98             }
 99         }
100     }
101     return 0;
102 }