记录编号	590968	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAATWTWTWWWWTWWWWWWTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTA
题目名称	[洛谷3950]部落冲突	最终得分	40
用户昵称	健康铀	是否通过	未通过
代码语言	C++	运行时间	110.113 s
提交时间	2024-07-14 15:26:48	内存使用	5.95 MiB

#include<bits/stdc++.h>
using namespace std;
int n,t,p,k,s[1200010],h[300010],maxx,tot,vis[300010],d1[300010],d2[300010],minx=1000001,m,res,zz[6010][3],cnt;
struct m{
    int ver,nx,ed;
}e[1200010];
void add(int x,int y){
    e[++tot].ver=y,e[tot].nx=h[x],e[tot].ed=1,h[x]=tot;
}
int dfs(int qd,int zd){
       memset(vis,0,sizeof(vis));
        queue <int> a;
        a.push(qd),vis[qd]=1;
        while(!a.empty()){
            int x=a.front();
            a.pop();
            for(int i=h[x];i;i=e[i].nx){
                int y=e[i].ver;
                if(!vis[y]&&e[i].ed==1)vis[y]=1,a.push(y);
            }
       }
       if(vis[zd]==1)
       return 1;
       else
       return 0;
}
void xg1(long long k,long long x,long long l,long long r){
    if(r<x||l>x){
        return;
    }
    if(l==r){
        s[k]=1; 
        return;
    }
    xg1(k*2,x,l,(r+l)/2);
    xg1(k*2+1,x,(r+l)/2+1,r);
    s[k]=s[k*2]+s[k*2+1];
}
 
void xg2(long long k,long long x,long long l,long long r){
    if(r<x||l>x){
        return;
    }
    if(l==r){
        s[k]=0; 
        return;
    }
    xg2(k*2,x,l,(r+l)/2);
    xg2(k*2+1,x,(r+l)/2+1,r);
    s[k]=s[k*2]+s[k*2+1];
}
void ask(long long k,long long x,long long y,long long l,long long r){
    if(l>y||r<x){
        return;
    }
    if(x<=l&&r<=y){
       res+=s[k];
       return;
    }
    ask(k*2,x,y,l,l+(r-l)/2);
    ask(k*2+1,x,y,l+(r-l)/2+1,r);
}
int main(){
    freopen("lct.in","r",stdin);
	freopen("lct.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    while(m--){
        char cd;
        int l,r,z;
        cin>>cd;
        if(cd=='Q'){
            cin>>l>>r;
           if(dfs(l,r)==1){
               cout<<"Yes"<<endl;
           } 
           else{
               cout<<"No"<<endl;
           }
        }
        else if(cd=='C'){
            cin>>l>>r;
            zz[++cnt][1]=l,zz[cnt][2]=r;
            for(int i=h[l];i;i=e[i].nx){
                int y=e[i].ver;
                if(y==r){
                    e[i].ed=0;
                    break;
                }
            }
            for(int i=h[r];i;i=e[i].nx){
                int y=e[i].ver;
                if(y==l){
                    e[i].ed=0;
                    break;
                }
            }
        }
        else{
            cin>>z;
            l=zz[z][1],r=zz[z][2];
            for(int i=h[l];i;i=e[i].nx){
                int y=e[i].ver;
                if(y==r){
                    e[i].ed=1;
                    break;
                }
            }
            for(int i=h[r];i;i=e[i].nx){
                int y=e[i].ver;
                if(y==l){
                    e[i].ed=1;
                    break;
                }
            }
        }
    }
    return 0;
}