线段树+标记永久化。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 100500
#define maxe 200500
using namespace std;
int n,q,x,y,nume=,g[maxv],w[maxv],hash[maxv],tot=,cnt=,mx[maxv];
int ls[maxv<<],rs[maxv<<],lazy[maxv<<],root;
char type[];
bool vis[maxv];
struct edge
{
int v,nxt;
}e[maxe];
void addedge(int u,int v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void dfs(int now)
{
w[now]=++cnt;hash[cnt]=now;mx[now]=w[now];
for (int i=g[now];i;i=e[i].nxt)
{
int v=e[i].v;
dfs(v);
mx[now]=max(mx[now],mx[v]);
}
}
void build(int &now,int left,int right)
{
now=++tot;lazy[now]=;
if (left==right) return;
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
}
void modify(int now,int left,int right,int l,int r,int p)
{
if ((left==l) && (right==r))
{
lazy[now]=max(lazy[now],p);
return;
}
int mid=(left+right)>>;
if (r<=mid) modify(ls[now],left,mid,l,r,p);
else if (l>=mid+) modify(rs[now],mid+,right,l,r,p);
else
{
modify(ls[now],left,mid,l,mid,p);
modify(rs[now],mid+,right,mid+,r,p);
}
}
int query(int now,int left,int right,int p)
{
if ((left==right) && (left==p)) return max(,lazy[now]);
int mid=(left+right)>>,regis=;
if (p<=mid) regis=query(ls[now],left,mid,p);
else regis=query(rs[now],mid+,right,p);
return max(regis,lazy[now]);
}
int main()
{
scanf("%d%d",&n,&q);vis[]=true;
for (int i=;i<=n-;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
}
dfs();
build(root,,cnt);
for (int i=;i<=q;i++)
{
scanf("%s",type);
if (type[]=='Q')
{
scanf("%d",&x);
printf("%d\n",hash[query(root,,cnt,w[x])]);
}
else
{
scanf("%d",&x);
if (!vis[x])
{
vis[x]=true;
modify(root,,cnt,w[x],mx[x],w[x]);
}
}
}
return ;
}