挺水的一道树剖，弄一下dfs序轻松解决。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int siz[N],son[N],dep[N],fa[N],dfn[N],top[N],yss[N],cnt;
inline int mmax(int x,int y){return dep[x]<dep[y]?y:x;}
struct SGT{int id;bool ex;}t[N<<3];
inline void update(int p){t[p].id=mmax(t[p<<1].id,t[p<<1|1].id);t[p].ex=t[p<<1].ex|t[p<<1|1].ex;}
void build(int p,int l,int r)
{
    if(l==r)
    {
        if(l==1)t[p].id=1,t[p].ex=1;
        return ;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    update(p);
}
void change(int p,int l,int r,int pos,int v)
{
    if(l==r){t[p].id=v;t[p].ex=1;return ;}
    int mid=l+r>>1;
    if(pos<=mid)change(p<<1,l,mid,pos,v);
    else change(p<<1|1,mid+1,r,pos,v);
    update(p);
}
int query(int p,int l,int r,int L,int R)
{
    if(!t[p].ex)return 0;
    if(L<=l&&R>=r)return t[p].id;
    int mid=l+r>>1,ls=0,rs=0;
    if(R>mid&&t[p<<1|1].ex)rs=query(p<<1|1,mid+1,r,L,R);
    if(L<=mid&&t[p<<1].ex)ls=query(p<<1,l,mid,L,R);
    return mmax(ls,rs);
}
struct edge{int y,next;}a[N<<1];int last[N],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs1(int x)
{
    siz[x]=1;son[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if((y=a[k].y)==fa[x])continue;
        fa[y]=x;dep[y]=dep[x]+1;
        dfs1(y);
        siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
    }
}
void dfs2(int x,int tp)
{
    dfn[x]=++cnt;yss[cnt]=x;top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=fa[x]&&y!=son[x])dfs2(y,y);
}
int n,m;
int solve(int x)
{
    while(top[x]!=1)
    {
        int val=query(1,1,n,dfn[top[x]],dfn[x]);
        if(val)return val;
        x=fa[top[x]];
    }
    return query(1,1,n,dfn[top[x]],dfn[x]);
}
int main()
{
    //freopen("tree11.in","r",stdin);
    //freopen("tree11.ans","w",stdout);
    qr(n),qr(m);
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
    dep[1]=1;dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        char op[2];int x;scanf("%s",op);qr(x);
        if(op[0]=='Q')qw(solve(x)),puts("");
        else change(1,1,n,dfn[x],x);
    }
    return 0;
}