http://www.zybbs.org/JudgeOnline/problem.php?id=1103

傻X题……那为什么要写题解呢……庆祝自己又一题RANK1呗……而且这次速度特别快……代码也很短，囧……

其实真正原因是为了纪念爆栈……用PAS的同学直接DFS递归就A掉了这题，我以为C也可以，没想到被坑了！！最后还是写了个栈，4行……唉……郁闷！

题解就是排出DFS序以后，W相当于查询一个点的权值，A相当于区间减1，就可以用树状数组维护。一开始忘了这样怎么维护了，就去看了看那时候R1的Tim神犇的代码，抄了下发现不行，结果发现我们的线段是不一样的……只好自己YY一个结果就对了- -！查询：S(x)；更新：I(b,1),I(a-1,-1)。

加了萎缩的i/o优化哦！33行～

#include <stdio.h>
#include <string.h>
int n,m,a[250002],pos[250000][2],f[250000]={-1},k,s=0,stack[250000],tmp[10];
char str[1000002],op[1400002],*p=str,*buf=op;
inline void I(x,y){if(x)for(;x<=n;x+=x&-x)a[x]+=y;}
inline S(x){int ans=0;for(;x;x-=x&-x)ans+=a[x];return ans;}
struct edge{struct edge *next;int y;}*map[250000],st[500000],*q;_Bool v[250000];
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')if(!*++p)fread(p=str,1,1000000,stdin);
	for(;*p>='0'&&*p<='9';*p||fread(p=str,1,1000000,stdin))re=re*10+*p++-48;
	return re;
}main(){
	int i=-2,x,y;
	for(m=(n=getint())-1<<1;(i+=2)!=m;){
		st[i].next=map[st[i^1].y=x=getint()-1];
		st[i^1].next=map[st[i].y=y=getint()-1];
		map[x]=st+i;map[y]=st+(i^1);
	}for(memset(f,-1,n<<2);s!=-1;)if(v[stack[s]])I(pos[stack[s--]][1]=k,-1);
	else{
		v[x=stack[s]]=1;I(pos[x][0]=k++,1);
		for(q=map[x];q;q=q->next)if(q->y!=f[x])f[stack[++s]=q->y]=x;
	}for(m=getint()+n-1;m--;){
		while(*p!='W'&&*p!='A')if(!*++p)fread(p=str,1,1000000,stdin);
		if(*p=='W'){
			if(!(y=S(pos[getint()-1][0])))*buf++=48;
			else{
				for(x=9;y;y/=10)tmp[x--]=y%10;
				while(++x!=10)*buf++=tmp[x]+48;
			}*buf++='\n';
		}else(x=getint()-1)==f[y=getint()-1]?(I(pos[y][1],1),I(pos[y][0],-1)):(I(pos[x][1],1),I(pos[x][0],-1));
	}return puts(op),0;
}

• inline
• block