#include <bits/stdc++.h>
using namespace std ;
int n , q ;
bool ybj[100010] ;
bool yy[400010] ;
int lt[100010] , dy[100010] , yt , hd[100010] ;
int size[100010] , fa[100010] ;
int fir[100010] , nxt[200010] , zx[200010] , bs ;
int dfs( int wz )
{
	size[wz] = 1 ;
	for( int i = fir[wz] ; i != -1 ; i = nxt[i] )
	{
		if( zx[i] != fa[wz] )
		{
			fa[zx[i]] = wz ;
			size[wz] += dfs( zx[i] ) ;
		}
	}
	return size[wz] ;
}
void dfs2( int wz )
{
	dy[wz] = yt ;
	hd[yt] = wz ;
	yt ++ ;
	if( nxt[fir[wz]] == -1 && fa[wz] != -1 ) return ;
	int maxx = zx[fir[wz]] ;
	if( maxx == fa[wz] ) maxx = zx[nxt[fir[wz]]] ;
	for( int i = fir[wz] ; i != -1 ; i = nxt[i] )
	{
		if( zx[i] != fa[wz] )
		{
			if( size[zx[i]] > size[maxx] )
			{
				maxx = zx[i] ;
			}
		}
	}
	lt[maxx] = lt[wz] ;
	dfs2( maxx ) ;
	for( int i = fir[wz] ; i != -1 ; i = nxt[i] )
	{
		if( zx[i] != fa[wz] && zx[i] != maxx )
		{
			lt[zx[i]] = zx[i] ;
			dfs2( zx[i] ) ;
		}
	}
	return ;
}
void xg( int wz , int l , int r , int mb )
{
	if( l > mb || r < mb ) return ;
	if( l == r )
	{
		yy[wz] = 1 ;
		return ;
	}
	int mid = ( l + r ) / 2 ;
	xg( wz * 2 , l , mid , mb ) ;
	xg( wz * 2 + 1 , mid + 1 , r , mb ) ;
	yy[wz] = 1 ;
	return ;
}
bool cx( int wz , int l , int r , int ll , int rr )
{
	if( rr < l || r < ll ) return false ;
	if( ll <= l && r <= rr )
	{
		return yy[wz] ;
	}
	int mid = ( l + r ) / 2 ;
	return cx( wz * 2 , l , mid , ll , rr ) || cx( wz * 2 + 1 , mid + 1 , r , ll , rr ) ;
}
int cz( int ww )
{
	while( !cx( 1 , 0 , n - 1 , dy[lt[ww]] , dy[ww] ) )
	{
		ww = fa[lt[ww]] ;
	}
	int l = dy[lt[ww]] , r = dy[ww] , ans = dy[lt[ww]] , mid ;
	while( l <= r )
	{
		mid = ( l + r ) / 2 ;
		if( cx( 1 , 0 , n - 1 , mid , ww ) )
		{
			ans = mid ;
			l = mid + 1 ;
		}
		else
		{
			r = mid - 1 ;
		}
	}
	return hd[ans] ;
}
int main ()
{
	memset( fir , -1 , sizeof(fir) ) ;
	scanf( "%d%d\n" , &n , &q ) ;
	int t1 , t2 ;
	char tt ;
	for( int i = 1 ; i < n ; i ++ )
	{
		scanf( "%d%d" , &t1 , &t2 ) ;
		t1 -- ;
		t2 -- ;
		nxt[bs] = fir[t1] ;
		fir[t1] = bs ;
		zx[bs] = t2 ;
		bs ++ ;
		nxt[bs] = fir[t2] ;
		fir[t2] = bs ;
		zx[bs] = t1 ;
		bs ++ ;
	}
	fa[0] = -1 ;
	dfs( 0 ) ;
	lt[0] = 0 ;
	dfs2( 0 ) ;
	xg( 1 , 0 , n - 1 , 0 ) ;
	scanf( "\n" ) ;
	for( int i = 0 ; i < q ; i ++ )
	{
		scanf( "%c %d" , &tt , &t1 ) ;
		t1 -- ;
		if( tt == 'C' )
		{
			xg( 1 , 0 , n - 1 , dy[t1] ) ;
		}
		else
		{
			printf( "%d\n" , cz( t1 ) + 1 ) ;
		}
		scanf( "\n" ) ;
	}
	return 0 ;
}

luogu 20pts

前两个dfs是书剖，中间两个函数是线段树，最后一函数个是二分

错误的点都比较偏后，平均是100个询问里有一个WA，偏大偏小不确定