反向操作，先把所有的标记都打上（记得统计标记的数目），然后依次撤销，合并到自己的上一个点pre，即fa[u]=getf(pre[u])
#include<cstdio>
#include<iostream>
#define R register int
using namespace std;
const int N=;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,k,cnt;
int vr[N<<],nxt[N<<],fir[N],fa[N],pre[N],c[N],ans[N],s[N];
char ch[N];
inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}
int getf(int x) {return x==fa[x]?x:fa[x]=getf(fa[x]);}
void dfs(int u,int f) { bool flg=true;
if(!fa[u]) fa[u]=f,flg=false;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(pre[v]) continue; pre[v]=u;
if(flg) dfs(v,u);
else dfs(v,f);
}
}
signed main() {
n=g(),k=g();
for(R i=,u,v;i<n;++i) u=g(),v=g(),add(u,v),add(v,u);
for(R i=;i<=k;++i) {
while(!isalpha(ch[i]=getchar())); c[i]=g();
if(ch[i]=='C') fa[c[i]]=c[i],++s[c[i]];
} fa[]=; pre[]=;
dfs(,); cnt=;
for(R i=k;i>=;--i) {
if(ch[i]=='C'&&!(--s[c[i]])) fa[c[i]]=getf(pre[c[i]]);
else if(ch[i]=='Q')ans[++cnt]=getf(c[i]);
} for(R i=cnt;i>=;--i) printf("%d\n",ans[i]);
}
2019.04.16
