poj3321——Apple Tree//树状数组

44424742

记住树状数组的基本操作：http://hi.baidu.com/wuxyy/blog/item/a4ad808b59be8bd2fd1f109d.html
http://writeblog.csdn.net/PostEdit.aspx?entryId=6376639
int lowbit(int x){   return x&(x^(x–1));}利用机器补码的特点，这个函数可以改得更方便int lowbit(int i){   return i&(-i);}如果要把a[n]增加m，可以通过调用如下函数实现void add(int i,int v){   while (i<=n)   {      a[i]+=v;      i+=lowbit(i);   }}如果要统计a[1]到a[n]之间的和，可以通过调用如下函数实现int sum(int i){   int s=0;   while (i>0)   {      s+=a[i];      i-=lowbit(i);   }   return s;}
此题思路：将每个点定一个时间戳。比如题目中给的树dfs()之后，点1为1,6，点2为2,3，点3为4,5.这样，查询1时，统计1--6之间的apple，再将结果除以2即可。
#include<iostream>#include<cstdio>#include<string>using namespace std;#define maxn 1000005int n,m;class map{public:int v,next;};map g[maxn];int head[maxn],cnt,c[maxn*2];bool have[maxn];class tree{public:int st,ed;};tree st[maxn];void dfs(int v){st[v].st =++cnt;int i;for(i=head[v];i;i=g[i].next ){dfs(g[i].v );}st[v].ed =++cnt;}int lowbit(int x){return x&(-x);}void add(int t,int v){while(t<maxn){c[t]+=v;t+=lowbit(t);}}int getsum(int t){int s=0;while(t>0){s+=c[t];t-=lowbit(t);}return s;}int main(){int i,a,b,lsum,rsum;char ch;cnt=0;scanf("%d",&n);for(i=1;i<n;i++){scanf("%d%d",&a,&b);g[++cnt].v =b;g[cnt].next =head[a];head[a]=cnt;}cnt=0;dfs(1);memset(have,true,sizeof(have));for(i=1;i<=n;i++){add(st[i].st,1);add(st[i].ed,1);}scanf("%d",&m);getchar();while(m--){scanf("%c %d",&ch,&a);getchar();if(ch=='Q'){lsum=getsum(st[a].st-1 );rsum=getsum(st[a].ed );printf("%d\n",(rsum-lsum)/2);}else if(ch=='C'){if(have[a]){have[a]=false;add(st[a].st ,-1);add(st[a].ed ,-1);}else {have[a]=true;add(st[a].st ,1);add(st[a].ed ,1);}}}return 0;}