dfs序

 1 /************************************************************** 2     Problem: 1103 3     User: Tunix 4     Language: C++ 5     Result: Accepted 6     Time:3884 ms 7     Memory:10060 kb 8 ****************************************************************/ 9  10 //BZOJ 110311 #include<cstdio>12 #include<cstring>13 #include<cstdlib>14 #include<iostream>15 #include<algorithm>16 #define rep(i,n) for(int i=0;i<n;++i)17 #define F(i,j,n) for(int i=j;i<=n;++i)18 #define D(i,j,n) for(int i=j;i>=n;--i)19 #define pb push_back20 using namespace std;21 void read(int &v){22     v=0; int sign=1; char ch=getchar();23     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();}25     v*=sign;26 }27 #define debug28 /******************tamplate*********************/29 const int N=250010;30 int head[N],to[N],next[N],cnt;31 void add(int x,int y){32     to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;33 }34 /********************edge**********************/35 int n,m,dfs_clock,t[N*2],l[N],r[N];36 inline int lowbit(int x){return x&(-x);}37 void update(int x,int val){38     for(int i=x;i<=n*2;i+=lowbit(i))39         t[i]+=val;40 }41 int sum(int x){42     int temp=0;43 //  for(int i=1;i<=x;++i) temp+=t[i];44     for(int i=x;i;i-=lowbit(i)) temp+=t[i];45     return temp;46 }47 int fa[N],st[N],top=0;48 void dfs(){49     st[++top]=1;50     while(top){51         int x=st[top];52         if (!l[x]){53             l[x]=++dfs_clock;54             for(int i=head[x];i;i=next[i])55                 st[++top]=to[i];56         }57         else{58             r[x]=++dfs_clock;59             top--;60         }61     }62 }63 int main(){64     read(n);65     int x,y;66     F(i,2,n){67         read(x); read(y);68         add(x,y);69     }70     dfs();71     memset(t,0,sizeof t);72     F(i,2,n) {update(l[i],1); update(r[i],-1);}73     char cmd[3];74     read(m);75     F(i,1,n+m-1){76         scanf("%s",cmd);77         if (cmd[0]==‘A‘){78             read(x); read(y);79             update(l[y],-1) ;update(r[y],1);80         }81         else{82             read(x);83             printf("%d\n",sum(l[x]));84         }85     }86     return 0;87 }