题目：****http://www.lydsy.com/JudgeOnline/problem.php?id=1103

先将该树处理成DFS序列，然后用树状数组维护，在首次进入的点出+1，最后退出的点处-1，然后查询时该点的前缀和-1即为答案。每次该边时就将对应的点进入和退出两个位置改成0就好了。总体的说，这是一道有思考性的树状数组题目。

代码：

#include <cstdio>

#include <stack>

#include <algorithm>

#include <cstdlib>

#include <cstring>

  

using namespace std;

  

#define MAXN 250001

#define lowbit(x)(((~(x))+1)&x)

  

int n,m;

  

struct edge {

    int t;

    edge *next;

    edge (){

        next=NULL;

    }

} *head[MAXN];

  

int dfs[MAXN*2];

int first[MAXN],last[MAXN];

int t[MAXN*2];

int IN[MAXN];

  

void INSERT(int s,int t){

    edge *p=new(edge);

    p->t=t;

    p->next=head[s];

    head[s]=p;

    p=new(edge);

    p->t=s;

    p->next=head[t];

    head[t]=p;

}

  

struct node {

    int v;

    edge *p;

    bool flag;

    node (int _v,edge *_p,bool _flag):v(_v),p(_p),flag(_flag){

    }

};

  

stack<node>s;

  

int N=0;

  

bool flag[MAXN];

  

void DFS(){

    memset(flag,true,sizeof(flag));

    while (!s.empty()){

        s.pop();

    }

    s.push(node(1,head[1],true));

    while (!s.empty()){

        node i=s.top();

        flag[i.v]=false;

        s.pop();

        if (i.flag){

            dfs[++N]=i.v;

            first[i.v]=N;

            i.flag=false;

        }

        if (i.p==NULL){

            dfs[++N]=i.v;

            last[i.v]=N;

        } else {

            s.push(node(i.v,i.p->next,false));

            if (!flag[i.p->t]){

                continue;

            }

            IN[i.p->t]=i.v;

            s.push(node(i.p->t,head[i.p->t],true));

        }

    }

}

  

void Add(int x,int y){

    while (x<=N) t[x]+=y,x+=lowbit(x);

}

  

int Suffsum(int x){

    int rec=0;

    while (x) rec+=t[x],x-=lowbit(x);

    return rec;

}

  

int main(){

    scanf("%d",&n);

    for (int i=0;i++<n;){

        head[i]=NULL;

    }

    for (int i=0;i++<n-1;){

        int s,t;

        scanf("%d%d",&s,&t);

        INSERT(s,t);

    }

    DFS();

    memset(t,0,sizeof(t));

    for (int i=0;i++<n;){

        Add(first[i],1);

        Add(last[i],-1);

    }

    scanf("%d",&m);

    m=m+n-1;

    while (m--){

        char c[1];

        scanf("%s",&c);

        if (c[0]=='A'){

            int x,y;

            scanf("%d%d",&x,&y);

            if (IN[x]==y){

                Add(first[x],-1);

                Add(last[x],1);

            } else {

                Add(first[y],-1);

                Add(last[y],1);

            }

        } else {

            int w;

            scanf("%d",&w);

            printf("%d\n",Suffsum(first[w])-1);

        }

    }

    return 0;

}