Apple Tree

///到底怎么建图了啊！！！！！！！！！#include<iostream>#include<cstdio>#include<cstring>#define MAXN 100005using namespace std;int c[MAXN],head[MAXN],low[MAXN],high[MAXN];bool visit[MAXN];int n,m,k,step=0;struct Edg  ///邻接表建树{    int adv;    int next;} edg[2*MAXN];int lowbit(int x){    return x&-x;}int sum(int x){    int ret=0;    while(x>0)    {        ret+=c[x];        x-=lowbit(x);    }    return ret;}void add(int x,int d){    while(x<=n)    {        c[x]+=d;        x+=lowbit(x);    }}void addege(int u,int v)   ///建图  树状变成线状的吧？？？u v是边的两个端点{    edg[k].adv=v;    edg[k].next=head[u];    head[u]=k; ///1 2 3 4 ~~~~    k++;}void dfs(int u)   ///深搜 重新标号{    int i;    low[u]=step;    step++;    visit[u]=true;    for(i=head[u]; i!=-1; i=edg[i].next)        if(!visit[edg[i].adv])            dfs(edg[i].adv);    high[u]=step;}/*31 21 33Q 1C 2Q 1这个可以用DFS来实现，每个节点记录第一次访问和最后一次访问时的编号，假设为l和r，那么区间[l,r]之间的所有编号是以此节点为根节点的子树的各个节点的编号，这样就把树转化为线性结构了，之后就是用树状数组来处理了*/int main(void){    int i,u,v;    bool f[MAXN];    char ch;    memset(head,-1,sizeof(head));    memset(visit,false,sizeof(visit));    memset(f,false,sizeof(f));    scanf("%d",&n);    k=1;    for(i=1; i<n; i++)    {        scanf("%d%d",&u,&v);        addege(u,v);        add(i,1);   ///初始化均有一个苹果    }    add(i,1);    dfs(1);    scanf("%d",&m);    while(m--)    {        getchar();        scanf("%c%d",&ch,&i);        if(ch==‘C‘)   ///更改的        {            if(!f[i])   ///有？？没有？？交替的   所以用bool f[]来控制            {                add(low[i],-1);                f[i]=true;            }            else            {                add(low[i],1);                f[i]=false;            }        }        else            printf("%d\n",sum(high[i])-sum(low[i]-1));    }    return 0;}/*#include<cstdio>#include<cstring>using namespace std;#define MAX 100005int edge[MAX<<1];//表示第i条边的终点int next[MAX<<1];//与第i条边同起点的下一条边的位置int head[MAX<<1];//以i为起点的第一条边的储存位置int low[MAX],high[MAX],c[MAX];bool visit[MAX];int cnt,n;int lowbit(int x){    return x&-x;}void update(int pos,int value) //更新pos的值{    int x=pos;    while(x<=n)    {        c[x]+=value;        x+=lowbit(x);    }}int get_sum(int pos)//求1到pos位置的和{    int x=pos,sum=0;    while(x>0)    {        sum+=c[x];        x-=lowbit(x);    }    return sum;}void insert(int i,int a,int b)//a起点,b终点{    edge[i]=b;    next[i]=head[a];    head[a]=i;}void dfs(int x,int pre){    low[x]=(++cnt);    for(int i=head[x]; i!=-1; i=next[i])        if(edge[i]!=pre)            dfs(edge[i],x);    high[x]=cnt;}int main(){    int m;    int a,b;    char op[5];    for(; ~scanf("%d",&n);)    {        cnt=0;        memset(head,-1,sizeof(head));        memset(next,-1,sizeof(next));        memset(c,0,sizeof(c));        for(int i=1,j=1; i<n; ++i)        {            scanf("%d%d",&a,&b);            insert(j++,a,b);            insert(j++,b,a);        }        dfs(1,-1);//遍历树        //初始化        for(int i=1; i<=n; ++i)            update(i,1);        memset(visit,false,sizeof(visit));        scanf("%d",&m);        for(int i=0; i<m; ++i)        {            scanf("%s%d",op,&a);            if(op[0]==‘C‘)//更新            {                if(visit[a])                {                    update(low[a],1);                    visit[a]=false;                }                else                {                    update(low[a],-1);                    visit[a]=true;                }            }            else//查询                printf("%d\n",gets_um(high[a])-get_sum(low[a]-1));        }    }    return 0;}*/