比赛 2024暑假C班集训E 评测结果 AAAAAAWWWWAAAWWWAAWWWWWWWAAWAWWWAAWWAWAAWWWAWWAAAAAAWAAWWAATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTA
题目名称 部落冲突 最终得分 31
用户昵称 彭欣越 运行时间 90.423 s
代码语言 C++ 内存使用 5.25 MiB
提交时间 2024-07-14 11:52:21
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=300010;
int n,m,head[N*2],tot,flag,cnt,mk[N*2];
struct node {
    int idx,nxt,t;
}e[N*2];
struct edge {
    int a,b;
}t[N*2]; 
void add (int x,int y) {
    e[++tot].idx=y;
    e[tot].t=y;
    e[tot].nxt=head[x];
    head[x]=tot;
}
void dfs (int u,int v) {
    for (int i=head[u];i;i=e[i].nxt) {
        if (mk[e[i].idx]==1||e[i].idx==0) continue;
        //cout << e[i].idx <<endl;
        if (e[i].idx==v) {
            flag=1;
            return;
        }
        mk[e[i].idx]=1;
        dfs(e[i].idx,v);
        mk[e[i].idx]=0;
        if (flag==1) return;
    }
}
int main () {
    freopen("lct.in","r",stdin);
    freopen("lct.out","w",stdout);
    cin >> n >> m;
    for (int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    while (m--) {
        char s;
        int a,b;
        cin >> s;
        if (s=='Q') {
            cin >> a >> b;
            mk[a]=1;
            flag=0;
            dfs(a,b);
            mk[a]=0;
            if (flag==1) cout << "Yes" <<endl;
            else cout << "No" <<endl;
        }else if (s=='C') {
            cin >> a >> b;
            for (int i=head[a];i;i=e[i].nxt) {
                if (e[i].idx==b) {
                    t[++cnt].a=i;
                    e[i].idx=0;
                    break;
                }
            }
            for (int i=head[b];i;i=e[i].nxt) {
                if (e[i].idx==a) {
                    t[cnt].b=i;
                    e[i].idx=0;
                    break;
                }
            }
        }else{
            cin >> a;
            e[t[a].a].idx=e[t[a].a].t;
            e[t[a].b].idx=e[t[a].b].t;
        }
    }
    return 0;
}