记录编号	600931	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	2856.[洛谷3950]部落冲突	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	4.892 s
提交时间	2025-05-21 20:27:23	内存使用	7.04 MiB

#include <bits/stdc++.h>
using namespace std;

const int MX=300010;

struct Ed{
    int t,nx;
}e[MX<<1];

struct Wr{
    int tm,u,v;
}w[MX];

int n,m,ec,h[MX],d[MX],p[MX],sz[MX],sn[MX],tp[MX],df[MX],dc;

int c[MX];
inline int lb(int x){return x&-x;}
void ad(int p,int v){for(;p<=n;p+=lb(p))c[p]+=v;}
int qr(int p){int r=0;for(;p;p-=lb(p))r+=c[p];return r;}

void ae(int u,int v){
    e[++ec].t=v;e[ec].nx=h[u];h[u]=ec;
    e[++ec].t=u;e[ec].nx=h[v];h[v]=ec;
}

void d1(int u){
    sz[u]=1;
    for(int i=h[u];i;i=e[i].nx){
        int v=e[i].t;
        if(v==p[u])continue;
        d[v]=d[u]+1;p[v]=u;
        d1(v);sz[u]+=sz[v];
        if(sz[v]>sz[sn[u]])sn[u]=v;
    }
}

void d2(int u,int t){
    df[u]=++dc;tp[u]=t;
    if(sn[u])d2(sn[u],t);
    for(int i=h[u];i;i=e[i].nx){
        int v=e[i].t;
        if(v!=p[u]&&v!=sn[u])d2(v,v);
    }
}

int qry(int u,int v){
    int r=0;
    while(tp[u]!=tp[v]){
        if(d[tp[u]]>d[tp[v]])swap(u,v);
        r+=qr(df[v])-qr(df[tp[v]]-1);
        v=p[tp[v]];
    }
    if(d[u]>d[v])swap(u,v);
    return r+=qr(df[v])-qr(df[u]);
}

int main(){
    freopen("lct.in","r",stdin);
    freopen("lct.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i){
        int u,v;scanf("%d%d",&u,&v);
        ae(u,v);
    }
    
    d1(1);d2(1,1);
    
    int cnt=0;
    char op[3];
    while(m--){
        scanf("%s",op);
        if(op[0]=='Q'){
            int u,v;scanf("%d%d",&u,&v);
            puts(qry(u,v)?"No":"Yes");
        }
        else if(op[0]=='C'){
            ++cnt;
            scanf("%d%d",&w[cnt].u,&w[cnt].v);
            if(d[w[cnt].u]<d[w[cnt].v])swap(w[cnt].u,w[cnt].v);
            ad(df[w[cnt].u],1);
        }
        else if(op[0]=='U'){
            int k;scanf("%d",&k);
            ad(df[w[k].u],-1);
        }
    }
    return 0;
}