比赛 |
2024暑假C班集训E |
评测结果 |
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
|
题目名称 |
部落冲突 |
最终得分 |
0 |
用户昵称 |
wzh0425 |
运行时间 |
199.840 s |
代码语言 |
C++ |
内存使用 |
10.61 MiB |
提交时间 |
2024-07-14 10:27:33 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int sc[600005][2],t;
int n,m,hd[600005],nxt[600005],ver[600005],vis[600005],bj[600005],tmp,idx;
void add(int x,int y){
ver[++idx]=y;
nxt[idx]=hd[x];
hd[x]=idx;
}
void dfs(int x,int ed){
if (x==ed){
tmp=1;
return;
}
for (int i=hd[x];i;i=nxt[i]){
int y=ver[i];
if (!vis[i]&&!bj[i]){
bj[i]=1;
dfs(y,ed);
bj[i]=0;
}
}
}
int main(){
freopen("lct.in","r",stdin);
freopen("lct.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for (int i=1;i<=m;i++){
char s;
int x,y;
scanf("%s",&s);
if (s=='Q'){
scanf("%d%d",&x,&y);
tmp=0;
dfs(x,y);
if (tmp==0) printf("No\n");
else printf("Yes\n");
}else if (s=='C'){
scanf("%d%d",&x,&y);
for (int j=hd[x];j;j=nxt[j]){
int yy=ver[j];
if (y==yy){
vis[j]=1;
sc[++t][0]=j;
break;
}
}
for (int j=hd[y];j;j=nxt[j]){
int xx=ver[j];
if (xx==x){
vis[j]=1;
sc[++t][1]=j;
break;
}
}
}else{
scanf("%d%d",&x);
vis[sc[x][0]]=0;
vis[sc[x][1]]=0;
}
}
return 0;
}