题面
Sol
每个被标记的点只会影响到它的子树，那么直接用线段树在dfn上搞
单点查询，区间修改
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 10);
IL ll Read(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, Q, fst[_], nxt[_], to[_], cnt, fa[_], dfn[_], deep[_], Index, id[_], ed[_];
int mx[_ << 2];
IL void Add(RG int u, RG int v){ to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt++; }
IL void Dfs(RG int u, RG int ff){
fa[u] = ff; deep[u] = deep[ff] + 1; dfn[u] = ++Index;
for(RG int e = fst[u]; e != -1; e = nxt[e]) Dfs(to[e], u);
ed[u] = Index;
}
IL void Update(RG int x, RG int y){ if(deep[mx[y]] > deep[mx[x]]) mx[x] = mx[y]; }
IL void Modify(RG int x, RG int l, RG int r, RG int L, RG int R, RG int p){
if(L <= l && R >= r){ if(deep[p] > deep[mx[x]]) mx[x] = p; return; }
RG int mid = (l + r) >> 1;
if(mx[x]) Update(x << 1, x), Update(x << 1 | 1, x), mx[x] = 0;
if(L <= mid) Modify(x << 1, l, mid, L, R, p);
if(R > mid) Modify(x << 1 | 1, mid + 1, r, L, R, p);
}
IL int Query(RG int x, RG int l, RG int r, RG int p){
if(l == r) return mx[x];
RG int mid = (l + r) >> 1;
if(mx[x]) Update(x << 1, x), Update(x << 1 | 1, x), mx[x] = 0;
if(p <= mid) return Query(x << 1, l, mid, p);
return Query(x << 1 | 1, mid + 1, r, p);
}
int main(RG int argc, RG char* argv[]){
n = Read(); Q = Read(); Fill(fst, -1);
for(RG int i = 1, x, y; i < n; ++i) x = Read(), y = Read(), Add(x, y);
Dfs(1, 0); mx[1] = 1;
for(RG int x; Q; --Q){
RG char op; scanf(" %c", &op); x = Read();
if(op == 'C') Modify(1, 1, n, dfn[x], ed[x], x);
else printf("%d
", Query(1, 1, n, dfn[x]));
}
return 0;
}