rt，本人在做这道题时使用了在线+染色，这是我第一次写的：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,q,u,v,s[maxn],son[maxn],fa[maxn],top[maxn],dfn[maxn],rnk[maxn],dep[maxn],tot;
vector<int>g[maxn];
char opt;
struct tree{
    int l,r,val;
}tr[maxn<<1];
void dfs1(int x,int f){
    fa[x]=f,dep[x]=dep[f]+1,s[x]=1;
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==f)
            continue;
        dfs1(to,x);
        s[x]+=s[to];
        if(!son[x]||s[son[x]]<s[to])
            son[x]=to;
    }
}
void dfs2(int x,int t){
    top[x]=t,dfn[x]=++tot,rnk[tot]=x;
    if(son[x])
        dfs2(son[x],t);
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==son[x]||to==fa[x])
            continue;
        dfs2(to,to);
    }
}
void push_up(int p){
    tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].val=0;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    push_up(p);
}
void update(int p,int x,int v){
    if(tr[p].l==tr[p].r){
        tr[p].val=v;
        return;
    }
    int mid=tr[p].l+tr[p].r>>1;
    if(mid>=x)
        update(p<<1,x,v);
    else update(p<<1|1,x,v);
    push_up(p);
}
int query(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)
        return tr[p].val;
    int mid=tr[p].l+tr[p].r>>1,ans=0;
    if(mid>=l)
        ans=max(ans,query(p<<1,l,r));
    if(mid<r)
        ans=max(ans,query(p<<1|1,l,r));
    return ans;
}
int linker(int u,int v){
    int ans=0;
    while(top[u]!=top[v]){
        if(dfn[top[u]]<dfn[top[v]])
            swap(u,v);
        ans=max(ans,query(1,dfn[top[u]],dfn[u]));
        u=fa[top[u]];
    }
    ans=max(ans,query(1,min(dfn[u],dfn[v]),max(dfn[u],dfn[v])));
    return ans;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0),dfs2(1,0),build(1,1,n);
    update(1,1,1);
    while(q--){
        cin>>opt>>u;
        if(opt=='C')
            update(1,dfn[u],u);
        if(opt=='Q')
            cout<<linker(u,1)<<"\n";
    }
    return 0;
}

此时WAon#12，而换成

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,q,u,v,s[maxn],son[maxn],fa[maxn],top[maxn],dfn[maxn],rnk[maxn],dep[maxn],tot;
vector<int>g[maxn];
char opt;
struct tree{
    int l,r,val;
}tr[maxn<<1];
void dfs1(int x,int f){
    fa[x]=f,dep[x]=dep[f]+1,s[x]=1;
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==f)
            continue;
        dfs1(to,x);
        s[x]+=s[to];
        if(!son[x]||s[son[x]]<s[to])
            son[x]=to;
    }
}
void dfs2(int x,int t){
    top[x]=t,dfn[x]=++tot,rnk[tot]=x;
    if(son[x])
        dfs2(son[x],t);
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==son[x]||to==fa[x])
            continue;
        dfs2(to,to);
    }
}
void push_up(int p){
    tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].val=0;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    push_up(p);
}
void update(int p,int x,int v){
    if(tr[p].l==tr[p].r){
        tr[p].val=v;
        return;
    }
    int mid=tr[p].l+tr[p].r>>1;
    if(mid>=x)
        update(p<<1,x,v);
    else update(p<<1|1,x,v);
    push_up(p);
}
int query(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)
        return tr[p].val;
    int mid=tr[p].l+tr[p].r>>1,ans=0;
    if(mid>=l)
        ans=max(ans,query(p<<1,l,r));
    if(mid<r)
        ans=max(ans,query(p<<1|1,l,r));
    return ans;
}
int linker(int u,int v){
    int ans=0;
    while(top[u]!=top[v]){
        if(dfn[top[u]]<dfn[top[v]])
            swap(u,v);
        ans=max(ans,query(1,dfn[top[u]],dfn[u]));
        u=fa[top[u]];
    }
    ans=max(ans,query(1,min(dfn[u],dfn[v]),max(dfn[u],dfn[v])));
    return ans;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0),dfs2(1,0),build(1,1,n);
    update(1,1,1);
    while(q--){
        cin>>opt>>u;
        if(opt=='C')
            update(1,dfn[u],dfn[u]);
        if(opt=='Q')
            cout<<rnk[linker(u,1)]<<"\n";
    }
    return 0;
}

就过了，为什么？麻烦dalao帮我这个小蒟蒻解答一下，悬1关