https://www.luogu.com.cn/record/187642490

#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fre(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
#define deb(x) freopen(x".in", "r", stdin); freopen(x".ans", "w", stdout);
#define endl "\n"
#define pb push_back

namespace Fast {
	void read(int &x) {
		int f = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			x = x * 10 + ch - '0';
			ch = getchar();
		}
		x *= f;
	}

	int read() {
		int x = 0, f = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			x = x * 10 + ch - '0';
			ch = getchar();
		}
		return x * f;
	}
}
using namespace Fast;

namespace zla {
	const int N = 100000 + 10;

	int n, q;
	vector<int> g[N];

	void add(int a, int b) {
		g[a].pb(b);
	}

	void Clear() {
		;
	}

	int dfn[N], sign, son[N], sz[N], top[N], fa[N];

	void dfs1(int u, int f) {
		sz[u] = 1;
		fa[u] = f;
		son[u] = -1;
		for (auto v : g[u]) {
			if (v == f) continue;
			dfs1(v, u);
			sz[u] += sz[v];
			if (son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
		}
	}

	void dfs2(int u, int tp) {
		dfn[u] = ++ sign;
		top[u] = tp;
		if (son[u] != -1) dfs2(son[u], tp);
		for (auto v : g[u]) {
			if (v == fa[u] || v == son[u]) continue;
			dfs2(v, v);
		}
	}

	int dp[N][20];

	void ST() { 
		for (int i = 1; i <= n; i ++ ) dp[i][0] = fa[i];
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= log2(n); j ++ )
				dp[i][j] = dp[dp[i][j - 1]][j - 1];
	} 

	namespace SEGMENTTREE {
		struct SegmentTree {
			int l, r, val;
		} tr[N << 2];

		void up(int k) {
			tr[k].val = tr[k << 1].val + tr[k << 1 | 1].val;
		}

		void Build(int k, int l, int r) {
			tr[k].l = l, tr[k].r = r;
			if (l == r) {
				if (l == 1) tr[k].val = 1;
				return ;
			}
			int mid = l + r >> 1;
			Build(k << 1, l, mid);
			Build(k << 1 | 1, mid + 1, r);
			up(k);
		}

		void Updata(int k, int x) {
			if (tr[k].l > x || tr[k].r < x) return ;
			if (x <= tr[k].l && tr[k].r <= x) {
				tr[k].val = 1;
				return ;
			}
			Updata(k << 1, x);
			Updata(k << 1 | 1, x);
			up(k);
		}

		int Query(int k, int l, int r) {
			if (tr[k].l > r || tr[k].r < l) return 0;
			if (l <= tr[k].l && tr[k].r <= r) return tr[k].val;
			return Query(k << 1, l, r) + Query(k << 1 | 1, l, r);
		}
	}
	using namespace SEGMENTTREE;

	int query(int x) {
		if (Query(1, dfn[x], dfn[x])) return x;
		while (!Query(1, dfn[top[x]], dfn[x])) x = fa[top[x]];
		while (!Query(1, dfn[x], dfn[x])) x = fa[x];
		return x;
	}

	void Init() {
		cin >> n >> q;
		for (int i = 1; i < n; i ++ ) {
			int a, b;
			cin >> a >> b;
			add(a, b);
			add(b, a);
		}
	}

	void Solve() {
		dfs1(1, -1);
		dfs2(1, 1);
		Build(1, 1, n);
		ST();
		while (q -- ) {
			char ch;
			int x;
			cin >> ch >> x;
			if (ch == 'C') {
				Updata(1, dfn[x]);
			} else {
				cout << query(x) << "\n";
			}
		}
	}

	void main() {
		Clear();
		Init();
		Solve();
	}
}

signed main() {
	IOS;
	// fre("tree");
	// deb("tree4");
	int T = 1;
	// cin >> T;
	while (T -- ) zla::main();
	return 0;
}