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