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

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

int n, q, s[100005], heavist[100005], x, y, tot, dfn[100005], st[100005], depth[100005], f[100005];

char op;

struct node {

	int x;

	bool operator < (const node& a) const {

		return depth[x] > depth[a.x];

	}

} ;

vector <int> v[100005];

set <node> black[100005];

void init1 (const int x, const int fa) {

	s[x] = 1, f[x] = fa;

	depth[x] = depth[fa] + 1;

	for (const int& i : v[x])
		if (i != fa) {

			init1 (i, x);

			s[x] += s[i];

			if (s[heavist[x]] < s[i])
				heavist[x] = i;

		}

	return ;

}

void init2 (const int x, const int fa, const int s) {

	st[x] = s;

	if (! heavist[x])
		return ;

	init2 (heavist[x], x, s);

	for (const int& i : v[x])
		if (i != fa && i != heavist[x])
			init2 (i, x, i);

	return ;

}

int find (int x) {

	while (st[x] ^ 1) {

		if (! black[st[x]].empty () && depth[y = black[st[x]].lower_bound ({x})->x] <= depth[x])
			return y;

		x = f[st[x]];

	}

	return black[1].lower_bound ({x})->x;

}

void change (const int x) {

	black[st[x]].insert ({x});

	return ;

}

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	cin >> n >> q;

	for (int i = 1; i < n; ++ i)
		cin >> x >> y, v[x].emplace_back (y), v[y].emplace_back (x);

	init1 (1, 0), init2 (1, 0, 1);

	black[1].insert ({1});

	while (q --) {

		cin >> op >> x;

		if (op == 'Q')
			cout << find (x) << '\n';
		else
			change (x);

	}

	I AK IOI

}