原题：P4092

下面代码复杂度应该是 $O(n\log^2n)$ 吧，如果是的话为什么会 TLE 三个点。

#include<bits/stdc++.h>
#define RG register
#define IL inline
using namespace std;
const int maxn = 100005;
const int maxm = 200005;
IL int Read(); IL void Rite(int x);
int n,q,head[maxm],cnt(-1);
int top[maxn],fth[maxn],ti,dfn[maxn],che[maxn];
int siz[maxn],son[maxn],dep[maxn];
bool tag[maxn]; set<int> s[maxn];
struct node{
	int to,nxt;
}edge[maxm];
void Input(int u,int v){
	edge[++cnt] = {v,head[u]};
	head[u] = cnt;
}
void DFS1(int u,int fa){
	dep[u] = dep[fa] + 1;
	fth[u] = fa;
	siz[u] = 1;
	for(int i = head[u];~i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == fa) continue;
		DFS1(v,u);
		siz[u] += siz[v];
		if(!son[u] || siz[son[u]] < siz[v])
			son[u] = v;
	}
}
void DFS2(int u,int tp){
	dfn[u] = ++ti;
	che[ti] = u;
	top[u] = tp;
	if(!son[u]) return;
	DFS2(son[u],tp);
	for(int i = head[u];~i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v != fth[u] && v != son[u])
			DFS2(v,v);
	}
}
int main(){
	memset(head,-1,sizeof(head));
	n = Read(); q = Read();
	for(int i = 1;i < n;++i){
		int u = Read(),v = Read();
		Input(u,v); Input(v,u);
	}
	DFS1(1,0); DFS2(1,1);
	tag[1] = 1;
	s[1].insert(dfn[1]);
	for(int i = 1;i <= q;++i){
		char c; c = getchar();
		while(c != 'C' && c != 'Q')
			c = getchar();
		int x = Read();
		if(c == 'C'){
			if(tag[x]) continue;
			tag[x] = 1;
			s[top[x]].insert(dfn[x]);
		} else {
			while(1){
				if(s[top[x]].size() == 0){
					x = fth[top[x]];		
					continue;
				}
				auto it = upper_bound(s[top[x]].begin(),s[top[x]].end(),dfn[x]);
				if(it == s[top[x]].begin()){
					x = fth[top[x]];
					continue;
				}
				it--;
				Rite(che[*it]); putchar('\n'); break;			
			}
		}
	}
	return 0;
}
IL int Read(){
	char c(getchar());
	int x(0),f(1);
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
IL void Rite(int x){
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) Rite(x / 10);
	putchar(x % 10 + '0');
}