思路大概是一种奇奇怪怪的树剖？

向子树大的那边延伸链，设链头为 h，对于操作 C，将 x 到 h 全打上一遍标记，对于操作 Q，若 h 的标记数减 x 标记数大于 1 则路径上有标记，直接暴搜，否则直接跳到 f[h] 继续判断

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int siz[maxn], f[maxn], bel[maxn], mar[maxn], vis[maxn], lest;
vector <int> e[maxn], h;
int get_size(int x, int fr) {
	f[x] = fr, siz[x] = 1;
	for (auto i : e[x]) if (i != fr) siz[x] += get_size(i, x);
	return siz[x];
}
void build_list(int x, int fr, int p, int len) {
	if (p == -1) h.push_back(x), p = x;
	bel[x] = h.size() - 1;
	int nex = 0; for (auto i : e[x]) if (i != fr && siz[i] >= siz[nex]) nex = i;
	if (len < lest) build_list(nex, x, p, len + 1); else nex = 0; //令链长不超过 logn, 以提升效率
	for (auto i : e[x]) if (i != fr && i != nex) build_list(i, x, -1, 1);
}
int query(int x) {
	if (vis[h[bel[x]]] > vis[x] || mar[x]) {
		while (!mar[x]) x = f[x];
		return x;
	}
	return query(f[h[bel[x]]]);
}
int main() {
	int n, q; scanf("%d%d", &n, &q);
	lest = ceil(log2(n));
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v);
		e[u].push_back(v), e[v].push_back(u);
	}
	get_size(1, -1), build_list(1, -1, -1, 1);
	mar[1] = vis[1] = 1;
	for (int i = 1; i <= q; i++) {
		char p; int x; scanf(" %c%d", &p, &x);
		if (p == 'C') {
			int rot = x; mar[x] = 1;
			while (rot != f[h[bel[x]]]) vis[rot] ++, rot = f[rot];
		} else printf("%d\n", query(x));
	}
}