这道题是可以用树链剖分来做的，但其实有比它更加简单的做法——并查集。
可以想到，这类题的一种常见做法是离线处理，先全部读入，再从后往前处理，每次遇到标记操作，就把这个点的标记次数减一，到零以后就把这个点的前继连到它的父亲上。
然后再倒序输出答案即可。
Code:
#include<cstdio>
#include<vector>
using namespace std;
;
struct data{
];
int dot;
}query[maxn];
int ans[maxn];
;
vector <int> a[maxn];
void readin(){
scanf("%d%d",&n,&q);
mark[]=;
; i<n; i++){
int u,v;
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
; i<=q; i++){
scanf("%s%d",query[i].str,&query[i].dot);
]=='C') mark[query[i].dot]++;
}
}
int find(int x){
if (par[x]==x) return x;
else return par[x]=find(par[x]);
}
void dfs(int s,int p){
if (mark[s]) par[s]=s;
else par[s]=find(p);
; i<a[s].size(); i++){
int now=a[s][i];
if (now==p) continue;
fa[now]=s;
dfs(now,s);
}
}
void solve(){
dfs(,);
; i--){
]=='Q'){
ans[++t]=find(query[i].dot);
}
else {
int now=query[i].dot;
mark[now]--;
) par[now]=find(fa[now]);
}
}
}
void putout(){
; i--) printf("%d\n",ans[i]);
}
int main(){
readin();
solve();
putout();
;
}