记录编号	590976	评测结果	WWWWWWWWWWWWWWWWWWWWWWWWWWWWWAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
题目名称	[洛谷3950]部落冲突	最终得分	30
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	13.058 s
提交时间	2024-07-14 17:23:34	内存使用	6.58 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 600010
int hd[MAXN],ed[MAXN],nxt[MAXN];
int fnt[MAXN],son[MAXN],siz[MAXN],dep[MAXN],num[MAXN],fat[MAXN];
int s[MAXN],fhtl[MAXN],fhtr[MAXN];
int n,m,cntz,cntU,cnt;
int lowbit(int idx){
    return idx&(-idx);
}
void ad_(int idx,int p){
    while(idx<=cntz){
        s[idx]+=p;
        idx+=lowbit(idx);
    }
}
int re_(int idx){
    int ans=0;
    while(idx>0){
        ans+=s[idx];
        idx-=lowbit(idx);
    }
    return ans;
}
void build(int x,int y){
    nxt[++cnt]=hd[x];
    hd[x]=cnt;
    ed[cnt]=y;
}
void dfs(int now,int fa){
//    cout<<now<<" "<<fa<<endl;
    fat[now]=fa;
    dep[now]=dep[fa]+1;
    siz[now]++;
    int maxz=0;
    for(int i=hd[now];i;i=nxt[i]){
        int y=ed[i];
//        cout<<i<<" "<<ed[i]<<endl;
        if(y!=fa){
//            cout<<"1"<<endl;
            dfs(y,now);
            if(siz[y]>maxz){
                maxz=siz[y];
                son[now]=y;
            }
        }
    }
}
void dfs2(int now,int fa,int p){
//    cout<<now<<" "<<fa<<" "<<p<<" "<<cntz<<endl;
    fnt[now]=p;
    num[now]=++cntz;
    if(son[now])dfs2(son[now],now,p);
    for(int i=hd[now];i;i=nxt[i]){
        int y=ed[i];
//        cout<<i<<" "<<y<<endl;
        if(y!=fa&&y!=son[now]){
            dfs2(y,now,y);
        }
    }
}
int qs(int x,int y){
//    cout<<"x:"<<x<<" y:"<<y<<" fntx"<<fnt[x]<<" fnty"<<fnt[y]<<" depx:"<<dep[x]<<" depy:"<<dep[y]<<endl;
    if(fnt[x]==fnt[y]){
//        cout<<re_(num[son[x]])-re_(num[y])<<" "<<re_(num[y])-re_(num[x])<<endl;
        if(dep[x]<dep[y])return re_(num[y])-re_(num[x]);
        else return re_(num[x])-re_(num[y]);
    }
    if(dep[fnt[x]]<dep[fnt[y]])swap(x,y);
//    cout<<"fntx"<<fnt[x]<<" "<<
    return re_(num[x])-re_(num[fat[fnt[x]]])+qs(fat[fnt[x]],y);
}
int main(){
    freopen("lct.in","r",stdin);
    freopen("lct.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        build(x,y);
        build(y,x);
    }
    dfs(1,1);
    dfs2(1,1,1);
    for(int i=1;i<=m;i++){
        char c;
        cin>>c;
        if(c=='C'){
            cin>>fhtl[++cntU]>>fhtr[cntU];
            if(dep[fhtl[cntU]]>dep[fhtr[cntU]]){
                ad_(num[fhtl[cntU]],1);
            }else{
                ad_(num[fhtr[cntU]],1);
            }
        }else if(c=='U'){
            int x;
            cin>>x;
            if(dep[fhtl[x]]>dep[fhtr[x]]){
                ad_(num[fhtl[x]],-1);
            }else{
                ad_(num[fhtr[x]],-1);
            }
        }else{
            int x,y;
            cin>>x>>y;
            if(qs(x,y)>0)cout<<"No\n";
            else cout<<"Yes\n";
        }
    }
    return 0;
}