首先我们可以做一遍dfs，用一个队列记录每个点进出的顺序，当每个点访问的时候que[tot++]=x，记为in[x]，当结束dfs的时候que[tot++]=x，记为out[x]，这样处理出来的队列，如果我们将一个数的进队赋值为1，出队赋值为-1，那么假设我们需要询问1-x的链中共有多少个点，答案就是这个队列前int[x]项，所以我们开始dfs1处理出来in,out数组，然后用树状数组维护这个队列，就行了。
/************************************************************** Problem: 1103 User: BLADEVIL Language: C++ Result: Accepted Time:4680 ms Memory:11300 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #define maxn 250010 using namespace std; int n,l,tot; int last[maxn],other[maxn],pre[maxn],in[maxn],out[maxn],w[maxn<<1]; char c[10]; void change(int x,int y) { while (x<=(n<<1)) { w[x]+=y; x+=x&(-x); } } int ask(int x) { int ans=0; while (x) { ans+=w[x]; x-=x&(-x); } return ans; } void connect(int x,int y) { pre[++l]=last[x]; last[x]=l; other[l]=y; } void dfs(int x,int fa) { in[x]=++tot; for (int q=last[x];q;q=pre[q]) { if (other[q]==fa) continue; dfs(other[q],fa); } out[x]=++tot; } int main() { scanf("%d",&n); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); connect(x,y); } dfs(1,-1); //for (int i=1;i<=n;i++) printf("%d %d %d ",i,in[i],out[i]); for (int i=2;i<=n;i++) change(in[i],1),change(out[i],-1); //for (int i=2;i<=2*n;i++) printf("%d ",ask(i)-ask(i-1)); printf(" "); int m; scanf("%d",&m); m+=n-1; while (m--) { int x,y; scanf("%s",&c); if (c[0]=='W') { scanf("%d",&x); //printf("x %d ",in[x]); printf("%d ",ask(in[x])); } else { scanf("%d%d",&x,&y); y=(x>y)?x:y; change(in[y],-1); change(out[y],1); //printf(" %d %d ",in[y],out[y]); } } return 0; }