样例以及自己打了的几个数据都能过。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int logto[23],fa[23][maxn],fmfa[maxn],depth[maxn];
char tree[maxn];
int n,father,cnt,opts;
void init() {
	logto[0]=1;
	for(int i=1; i<=22; i++)logto[i]=logto[i>>1]+1;
}
void update() {
	cnt++,opts++;
	cin>>tree[cnt];
	fa[0][cnt]=father;
	depth[cnt]=depth[father]+1;
	for(int i=1; i<=22; i++) {
		fa[i][cnt]=fa[i-1][fa[i-1][cnt]];
	}
	fmfa[opts]=cnt;
	father=cnt;
}
void Undo(int x) {
	opts++;
	father=fmfa[opts-x-1];
	fmfa[opts]=father;
}
void query(int x) {
	int now=father;
	for(int i=22; i>=0; i--) {
		if(depth[now]-logto[i]>=x) {
			now=fa[i][now];
		}
		if(depth[now]==x) {
			cout<<tree[now]<<'\n';
			break;
		}
	}
}
int main() {
	char opt;
	int x;
	init();
	cin>>n;
	while(n--) {
		cin>>opt;
		switch(opt) {
			case 'U':
				cin>>x;
				Undo(x);
				break;
			case 'Q':
				cin>>x;
				query(x);
				break;
			case 'T':
				update();
				break;
		}
	}
}