【注意事项】
为了体现增强版，题目限制和数据范围有所增强:
时间限制：1.5s
内存限制：128MB
对于15% 的数据，1<=N,Q<=1000.
对于35% 的数据，1<=N,Q<=10000.
对于50% 的数据，1<=N,Q<=100000,且数据均为官方数据.
对于100% 的数据，1<=N,Q<=1000000.
请注意常数因子对于程序运行的影响。
并查集很简单，并查集就是倒序处理，表示删除一个点的标记，删除后不会再加回来，删完后，合并当前点与其father的集合，根为father的原来的根，具体看代码……
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N=;
int cnt,fir[N],to[N*],nxt[N*];
void addedge(int a,int b){
nxt[++cnt]=fir[a];
to[fir[a]=cnt]=b;
}
int fa[N],vis[N],pre[N];
int qr[N],tp[N],ans[N];
void DFS(int x){
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=pre[x]){
pre[to[i]]=x;
DFS(to[i]);
}
}
void DFS(int x,int f){
fa[x]=f;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=pre[x]){
if(!vis[to[i]])DFS(to[i],f);
else DFS(to[i],to[i]);
}
}
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
int n,Q;char op[];
int main(){
freopen("tree++.in","r",stdin);
freopen("tree++.out","w",stdout);
int sz=<<;
char*p=(char*)malloc(sz)+sz;
__asm__("movl %0,%%esp\n"::"r"(p));
scanf("%d%d",&n,&Q);
for(int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}DFS();
for(int i=;i<=Q;i++){
scanf("%s%d",op,&qr[i]);
tp[i]=op[]=='Q'?:;
}
vis[]=;
for(int i=;i<=Q;i++)
if(tp[i])vis[qr[i]]+=;
DFS(,);
for(int i=Q;i>=;i--){
if(!tp[i])
ans[i]=Find(qr[i]);
else{
if(!--vis[qr[i]]){
int x=qr[i];
fa[x]=Find(pre[x]);
}
}
}
for(int i=;i<=Q;i++)
if(!tp[i])printf("%d\n",ans[i]);
return ;
}
树链剖分很好想，但慢了些。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
const int N=;
int cnt,fir[N],nxt[N*],to[N*];
void addedge(int a,int b){
nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;
nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;
}
int sz[N],son[N],fa[N],dep[N];
void DFS(int x){sz[x]=;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]){
dep[to[i]]=dep[fa[to[i]]=x]+;
DFS(to[i]);sz[x]+=sz[to[i]];
if(sz[son[x]]<sz[to[i]])son[x]=to[i];
}
}
int tot,id[N],rid[N],top[N];
void DFS(int x,int tp){
top[rid[id[x]=++tot]=x]=tp;
if(son[x])DFS(son[x],tp);
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
DFS(to[i],to[i]);
}
int sum[N*],pos[N*];
#define mid (l+r>>1)
void Push_up(int x){
sum[x]=sum[x<<]+sum[x<<|];
if(sum[x]==)pos[x]=;
if(sum[x<<|])pos[x]=pos[x<<|];
else pos[x]=pos[x<<];
}
void Update(int x,int l,int r,int g){
if(l==r){pos[x]=rid[l];sum[x]+=;return;}
if(mid>=g)Update(x<<,l,mid,g);
else Update(x<<|,mid+,r,g);
Push_up(x);
} int Query(int x,int l,int r,int a,int b){
//if(!sum[x])return 0;
if(l>=a&&r<=b)return pos[x];int ret=;
if(mid<b)ret=Query(x<<|,mid+,r,a,b);
if(!ret&&mid>=a)ret=Query(x<<,l,mid,a,b);
return ret;
} int tag[N],n,Q,x;
int Solve(int x){
while(x){
int d=Query(,,n,id[top[x]],id[x]);
if(d)return d;x=fa[top[x]];
}
return ;
}
char op[],c;
void read(int &x){
x=;while(c=getchar(),c>''||c<'');
while(x=x*+(c^),c=getchar(),c>=''&&c<='');
}
int main(){
freopen("tree++.in","r",stdin);
freopen("tree++.out","w",stdout);
read(n);read(Q);
int size = << ; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p));
for(int i=,a,b;i<n;i++){
read(a);read(b);
addedge(a,b);
}
DFS();DFS(,);
Update(,,n,);tag[]=;
while(Q--){
scanf("%s",op);read(x);
if(op[]=='C'){
if(tag[x])continue;
Update(,,n,id[x]);
tag[x]=;
}
else{
printf("%d\n",Solve(x));
}
}
//printf("%.2f\n",1.0*clock()/CLOCKS_PER_SEC);
return ;
}