比赛 |
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;
}