此题树剖裸题，但是并不想写线段树，于是就写了并查集 ，发现好像题解里并没有我这种做法，就写了这篇题解。

题解

我的做法是离线操作，在读入时记录每个点被染色的次数，之后从根节点dfs，如果这个点被染色了，就让并查集数组的值为自己，否则为他的父亲。 然后倒序枚举操作，如果是查询操作，直接find()这个点，得到的值就是最近的被染色的祖先，如果是标记操作，则删除这个标记，即让这个点被染色的次数减1，如果染色次数变成了0，就意味着这个点没有染色了，将并查集数组的值改为它的父亲。

代码

#include <cstdio>
const int MAXN=100010;
struct P {
    bool ty;
    int id,ans;
}p[MAXN];
int edv[MAXN<<1],ednxt[MAXN<<1];
int first[MAXN],cnt=0;
void add(int x,int y) {
    edv[++cnt]=y;
    ednxt[cnt]=first[x];
    first[x]=cnt;
}
int col[MAXN];
char inp[3];
int ufs[MAXN];  //并查集数组
int f[MAXN];	//记录一个点的父亲
void dfs(int x,int fa) {
    if(col[x]) ufs[x]=x;   //如果有染色，就让值等于自己
    else ufs[x]=fa;        //否则等于父亲
    f[x]=fa;
    for(int i=first[x];i;i=ednxt[i]) {
        int v=edv[i];
        if(v==fa) continue;
        dfs(v,x);
    }
}
int find(int x) {
    return x==ufs[x]?x:ufs[x]=find(ufs[x]);
}
int main() {
    int n,q;
    scanf("%d%d",&n,&q);
    int in1,in2;
    for(int i=1;i<n;++i) {
        scanf("%d%d",&in1,&in2);
        add(in1,in2);
        add(in2,in1);
    }
    col[1]=1;
    for(int i=1;i<=q;++i) {
        scanf("%s%d",inp,&p[i].id);
        switch(inp[0]) {
            case 'Q':{
                p[i].ty=0;
                break;
            }
            case 'C':{
                p[i].ty=1;
                ++col[p[i].id];
                break;
            }
        }
    }
    dfs(1,0);
    f[1]=1;
    for(int i=q;i>=1;--i) {
        if(p[i].ty) {
            --col[p[i].id];
            if(!col[p[i].id]) ufs[p[i].id]=f[p[i].id];  //这个点没有染色了
        } else {
            p[i].ans=find(p[i].id);
        }
    }
    for(int i=1;i<=q;++i) {
        if(!p[i].ty) {
            printf("%d\n",p[i].ans);
        }
    }
    return 0;
}

如果强制在线就GG了

树剖、LCT、离线见鬼去吧。

只需要普通的 dfs 序以及树上前缀和（差分）就可以了。

考虑树上前缀和，有标记为 $0$，否则为标记次数，显然用树状数组维护。

修改就是将节点 $u$ 的所有子树的前缀和值加 $1$，树状数组区间加即可，所以这里用的树状数组是区间加，单点查询的树状数组。

考虑查询，比较暴力的方法是二分答案与 $u$ 的深度差，再用类似倍增法 LCA 的方式得到当前二分的答案是那个点，直接差分判断即可，时间复杂度是 $\operatorname{O}(n\log^2n)$。

但实际上不用这么麻烦，倍增法 LCA 的最后一步就是直接贪心，如果直跳向上 $2^i$ 步不是答案，那就让 LCA 的两个点同时往上跳 $2^i$ 步（$i$ 从大到小枚举），这里也可以用一样的方式来求，但时间复杂度就还是 $\operatorname{O}(n\log^2n)$，因为查询需要时间，不过也能过。

用分块可以做到 $\operatorname{O}(n\sqrt n)$，但我没写。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100005][18],sz[100005],dep[100005],pos[100005],cnt;
vector<int>g[100005];
void dfs(int x,int fa){
	pos[x]=++cnt;
	f[x][0]=fa;
	sz[x]=1;
	for(auto y:g[x]){
		if(y==fa)continue;
		dep[y]=dep[x]+1;
		dfs(y,x);
		sz[x]+=sz[y];
	}
}
int t[100005];
inline void add(int x,int d){
	while(x<=n){
		t[x]+=d;
		x+=x&-x;
	}
}
int ask(int x){
	int ans=0;
	while(x){
		ans+=t[x];
		x-=x&-x;
	}
	return ans;
}
inline void update(int l,int r,int c){
	add(l,c);
	add(r+1,-c);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dep[1]=1;
	dfs(1,1);
	add(1,1);
	for(int i=1;i<=__lg(n);i++){
		for(int j=1;j<=n;j++){
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	while(m--){
		char op;
		int u;
		cin>>op>>u;
		if(op=='C'){
			update(pos[u],pos[u]+sz[u]-1,1);
		}else if(op=='Q'){
			for(int i=__lg(dep[u]);i>=0;--i){
				if(ask(pos[f[u][i]])==ask(pos[u])){
					u=f[u][i];
				}
			}
			cout<<u<<"\n";
		}
	}
	return 0;
}