#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; void Rd(int&res){ res=0;char c; while(c=getchar(),c<48); do res=res*10+(c&15); while(c=getchar(),c>47); } const int N=100005; int n,q,tot_edge,head[N]; struct Edge{ int to,nxt; }edge[N<<1]; void add_edge(int a,int b){ edge[tot_edge]=(Edge){b,head[a]}; head[a]=tot_edge++; } int tot_node,L[N],R[N],dep[N],fa[N][21]; void dfs(int p,int f,int d){ L[p]=++tot_node; dep[p]=d,fa[p][0]=f; for(int i=head[p];~i;i=edge[i].nxt){ int to=edge[i].to; if(to==f)continue; dfs(to,p,d+1); } R[p]=tot_node; } struct Segment_Tree{ struct node{ int L,R,mx,flag; }tree[N<<2]; void build(int L,int R,int p){ tree[p].L=L,tree[p].R=R,tree[p].mx=0; tree[p].flag=0; if(L==R)return; int mid=L+R>>1; build(L,mid,p<<1); build(mid+1,R,p<<1|1); } void up(int p){ tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx); } void down(int p){ if(tree[p].flag){ tree[p<<1].mx=max(tree[p<<1].mx,tree[p].flag); tree[p<<1|1].mx=max(tree[p<<1|1].mx,tree[p].flag); tree[p<<1].flag=max(tree[p<<1].flag,tree[p].flag); tree[p<<1|1].flag=max(tree[p<<1|1].flag,tree[p].flag); tree[p].flag=0; } } void update(int L,int R,int v,int p){ if(tree[p].L==L&&tree[p].R==R){ tree[p].flag=max(tree[p].flag,v); tree[p].mx=max(tree[p].mx,v); return; } down(p); int mid=tree[p].L+tree[p].R>>1; if(R<=mid)update(L,R,v,p<<1); else if(L>mid)update(L,R,v,p<<1|1); else update(L,mid,v,p<<1),update(mid+1,R,v,p<<1|1); up(p); } int query(int x,int p){ if(tree[p].L==tree[p].R){ return tree[p].mx; } down(p); int mid=tree[p].L+tree[p].R>>1; if(x<=mid)return query(x,p<<1); else return query(x,p<<1|1); } }T; void up(int&p,int step){ for(int i=0;i<=20;i++){ if(step&(1<<i))p=fa[p][i]; } } int main(){ memset(head,-1,sizeof(head)); Rd(n),Rd(q); for(int i=1,a,b;i<n;i++){ Rd(a),Rd(b); add_edge(a,b); add_edge(b,a); } dfs(1,0,0); for(int j=1;j<=20;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } T.build(1,n,1); for(int i=1;i<=q;i++){ char op[2]; int p; scanf("%s %d",op,&p); if(op[0]=='Q'){ int ans_dep=T.query(L[p],1); up(p,dep[p]-ans_dep); printf("%d\n",p); }else{ T.update(L[p],R[p],dep[p],1); } } return 0; }
|