poj3321-dfs序&树状数组&dfs序模板题-Apple Tree

开始用getsum()-getsum()当作单点查询竟然tle了。。

于是乎 我用了一个计数器。

和上一道题一摸一样。真的是模板题啊 亲们qwq

就对着照了上一道题改了一下下

一棵树上每个点上挂一个苹果

下列操作：① 查询以x为根的子树上有多少个苹果（裸的我tm）

② 对苹果的数量进行取反（如果有变成没有，没有变成有）

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
/*
体现题意的地方，就在于在树状数组中的结果。

*/
const int maxn=+;
struct Node{
    int to,next;
}node[maxn*];
int head[maxn];
int sta[maxn];
int end1[maxn];
int ans[maxn];
int sum[maxn];
int che[maxn];
int len;
void addedge(int a,int b){
     node[len].to=b;
     node[len].next=head[a];
     head[a]=len++;
}
int tim;
void init(){
    tim=;
    len=;
    memset(head,-,sizeof(head));
    memset(sta,,sizeof(sta));
    memset(sum,,sizeof(sum));
    memset(che,,sizeof(che));
}
void dfs(int s,int pre){
    sta[s]=++tim;
    for(int i=head[s];i!=-;i=node[i].next){
         int to=node[i].to;
         if(to==pre) continue;
         dfs(to,s);
    }
    end1[s]=tim;
}
int lowbit(int a){
    return a&(-a);
}
void add(int s,int va){
    for(int i=s;i<maxn;i+=lowbit(i))
        sum[i]+=va;
}
int getsum(int s){
     int all=;
     while(s>){
         all+=sum[s];
         s-=lowbit(s);
     }

     return all;
}
int main()
{   int m,n,a,b;
    while(~scanf("%d",&m)){
          if(!m)break;
          init();
          for(int i=;i<m-;i++){
              scanf("%d%d",&a,&b);
              addedge(a,b);
              addedge(b,a);
          }
          dfs(,-);
          scanf("%d",&n);
          char ch;
          for(int i=;i<=m;i++){
             add(sta[i],);
          }
          int nu;
          for(int i=;i<=n;i++){
              scanf(" %c",&ch);
              if(ch=='Q')
            {   scanf("%d",&nu);
                int ans=getsum(end1[nu])-getsum(sta[nu]-);
                printf("%d\n",ans);
            }
            else{
                 scanf("%d",&nu);
                 if(che[nu]%==){
                    che[nu]++;
                    add(sta[nu],-);
                 }
                 else{
                     che[nu]++;
                     add(sta[nu],);
                 }
            }
          }
          printf("\n");
    }
    return ;
}