思路：用数组模拟指针建图，dfs得到每个节点对应的开始时间擢和结束时间擢，然后用树状数组解决。
#include<iostream> using namespace std; #define maxn 100005 struct node { int ver,next; }; node g[maxn]; int adj[maxn],begin[maxn],end[maxn],c[maxn],time,e; bool app[maxn]; void insert(int u,int v) { g[e].ver=v,g[e].next=adj[u],adj[u]=e++; } void dfs(int v) { time++; app[v]=true; begin[v]=time; for(int i=adj[v];i!=-1;i=g[i].next) dfs(g[i].ver); end[v]=time; } int low(int k) { return k&(-k); } void update(int x,int n,int a) { while(x<=n) { c[x]+=a; x+=low(x); } return ; } int query(int x) { int sum=0; while(x>0) { sum+=c[x]; x-=low(x); } return sum; } int main() { int n,m,u,v,i,x; char chr; scanf("%d",&n); time=e=0; memset(adj,-1,sizeof(adj)); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); insert(u,v); } dfs(1); memset(c,0,sizeof(c)); scanf("%d",&m); getchar(); for(i=1;i<=m;i++) { scanf("%c%d",&chr,&x); getchar(); if(chr=='C') { if(app[x]) update(begin[x],time,-1); else update(begin[x],time,1); app[x]=app[x]^1; } else printf("%d/n",end[x]-begin[x]+1+ query(end[x])-query(begin[x]-1)); } return 0; }
