比赛 2024暑假C班集训E 评测结果 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
题目名称 部落冲突 最终得分 0
用户昵称 Untitled 运行时间 18.181 s
代码语言 C++ 内存使用 5.66 MiB
提交时间 2024-07-14 10:27:48
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

int n,m,idx,f[300010],dep[6010],w[6010][2];
bool g[6010][6010],solve2;


bool judge(int p,int q){
    if (dep[p]<dep[q]) swap(p,q);
    while (dep[p]>dep[q]){
        if (g[f[p]][p]) return 0;
        p=f[p];
    }
    while (p!=q){
        if (g[f[p]][p] || g[f[q]][q]) return 0;
        p=f[p],q=f[q];
    }
    return 1;
}

int main(){
    freopen("lct.in","r",stdin);
    freopen("lct.out","w",stdout);
    
    cin.tie(0);cout.tie(0);
    int p,q;
    char c;
    cin>>n>>m;
    for (int i=1;i<n;i++){
        cin>>p>>q;
        if (p<q) swap(p,q);
        f[p]=q;
    }
    if (n>=40000) solve2=1;
    if (!solve2) for (int i=2;i<=n;i++) dep[i]=dep[f[i]]+1;
    for (int x=1;x<=m;x++){
        cin>>c;
        if (c=='U') cin>>p;
        else cin>>p>>q;
        if (c=='Q'){
            if (solve2){
                if (p>q) swap(p,q);
                bool fl=0;
                for (int i=1;i<=idx;i++){
                    if (p<=w[i][0] && w[i][1]<q && g[w[i][0]][w[i][1]]) {
                        fl=1;
                        cout<<"No\n";
                        break;
                    }
                }
                if (!fl) cout<<"Yes\n";
            }
            else if (judge(p,q)) cout<<"Yes\n";
            else cout<<"No\n";
        }
        if (c=='C'){
            w[++idx][0]=p,w[++idx][1]=q;
            g[p][q]=1,g[q][p]=1;
        }
        else{
            g[w[p][0]][w[p][1]]=0,g[w[p][1]][w[p][0]]=0;
        }
    }
    
    return 0;
}