似乎是弱化的qtree3。树剖什么的非常无脑。考虑离线。并查集维护每个点的最近打标记祖先，倒序处理，删除标记时将其与父亲合并即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<stack> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')) c=getchar();return c;} #define N 100010 int n,m,p[N],cnt[N],fa[N],f[N],t; bool flag[N]; stack<int> v; struct data{int to,nxt; }edge[N]; struct data2{int op,x; }q[N]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} void dfs(int k,int from) { if (cnt[k]) fa[k]=k;else fa[k]=from; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) f[edge[i].to]=k,dfs(edge[i].to,k); } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} int main() { #ifndef ONLINE_JUDGE freopen("bzoj4551.in","r",stdin); freopen("bzoj4551.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<n;i++) { int x=read(),y=read(); addedge(x,y); } for (int i=1;i<=m;i++) q[i].op=getc()=='C',q[i].x=read(),cnt[q[i].x]+=q[i].op; cnt[1]++;dfs(1,1); for (int i=m;i>=1;i--) if (q[i].op) { cnt[q[i].x]--; if (!cnt[q[i].x]) fa[q[i].x]=find(f[q[i].x]); } else v.push(find(q[i].x)); while (!v.empty()) printf("%d ",v.top()),v.pop(); return 0; }