#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,msh[200009][19],dp[200009],lf[200009],rg[200009],tim,st[200009],shv[200009],dep[200009],f[200009],lc,E,C,D;
int fen1[200009],fen2[200009];
pair <char, pair <int, int> > p[1000009];
vector <int> v[200009];
void upd1(int q, int w){
while(q<=200001){
fen1[q]+=w;
q=q+(q&(-q));
}
}
int read1(int q){
int sm=0;
while(q>=1){
sm+=fen1[q];
q=q-(q&(-q));
}
return sm;
}
void upd2(int q, int w){
while(q<=200001){
fen2[q]+=w;
q=q+(q&(-q));
}
}
int read2(int q){
int sm=0;
while(q>=1){
sm+=fen2[q];
q=q-(q&(-q));
}
return sm;
}
bool anc(int q, int w){
if(lf[q]<=lf[w]&&rg[w]<=rg[q]) return 1; else return 0;
}
int lca(int q, int w){
if(anc(q,w)) return q;
if(anc(w,q)) return w;
for(int h=17; h>=0; h--){
if(msh[q][h]!=0&&anc(msh[q][h],w)==0){
q=msh[q][h];
}
}
return msh[q][0];
}
int upto(int q, int w){
for(int h=17; h>=0; h--){
if(msh[q][h]!=0&&anc(msh[q][h],w)==0){
q=msh[q][h];
}
}
return q;
}
void dfsst(int q, int w){
dep[q]=dep[w]+1;
msh[q][0]=w;
for(int h=1; h<=17; h++) msh[q][h]=msh[msh[q][h-1]][h-1];
//tim++;lf[q]=rg[q]=tim;
dp[q]=1;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfsst((*it),q);
dp[q]+=dp[(*it)];
//if(rg[(*it)]>rg[q]) rg[q]=rg[(*it)];
}
}
void dfs(int q, int w, bool BO){
tim++;lf[q]=rg[q]=tim;
if(BO==0){
st[q]=q;
}
if(q!=1&&v[q].size()==1) return;
if(v[q].size()==0) return;
int MX=0;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
if(dp[(*it)]>dp[MX]) MX=(*it);
}
shv[q]=MX;st[shv[q]]=st[q];
dfs(shv[q],q,1);
if(rg[MX]>rg[q]) rg[q]=rg[MX];
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w||(*it)==shv[q]) continue;
dfs((*it),q,0);
if(rg[(*it)]>rg[q]) rg[q]=rg[(*it)];
}
}
void UP1(int q){
if(anc(q,lc)) return;
int w=0;if(lf[st[q]]>lf[lc]) w=st[q]; else w=upto(q,lf[lc]);
if(lf[q]-lf[w]==read1(lf[q])-read1(lf[w]-1)){
}else{
E=1;
return;
}
if(msh[w][0]!=lc){
if(f[msh[w][0]]==-1||f[msh[w][0]]>f[w]||f[w]==-1){
E=1;
return;
}
}
UP1(msh[w][0]);
}
void UP2(int q){
if(anc(q,lc)) return;
int w=0;if(lf[st[q]]>lf[lc]) w=st[q]; else w=upto(q,lf[lc]);
if(lf[q]-lf[w]==read2(lf[q])-read2(lf[w]-1)){
}else{
E=1;
return;
}
if(msh[w][0]!=lc){
if(f[msh[w][0]]==-1||f[msh[w][0]]<f[w]||f[w]==-1){
E=1;
return;
}
}
UP2(msh[w][0]);
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>tes;
tes=tes+a-1;
for(t=1; t<=tes; t++){
cin>>p[t].first;
if(p[t].first=='S'){
cin>>p[t].second.first>>p[t].second.second;
v[p[t].second.first].push_back(p[t].second.second);
v[p[t].second.second].push_back(p[t].second.first);
}
if(p[t].first=='Q'){
cin>>p[t].second.first>>p[t].second.second;
}
if(p[t].first=='C'){
cin>>p[t].second.first;
}
}
dfsst(1,0);
dfs(1,0,0);
for(i=1; i<=a; i++) f[i]=-1;
/*for(i=1; i<=a; i++){
cout<<lf[i]<<" "<<shv[i]<<" "<<st[i]<<endl;
}*/
for(t=1; t<=tes; t++){
if(p[t].first=='S'){
c=p[t].second.first;d=p[t].second.second;
if(msh[c][0]==d) swap(c,d);
f[d]=t;
if(shv[d]!=0){
if(f[shv[d]]!=-1){
upd2(lf[d],1);
}
}
if(st[d]!=d){
if(f[c]!=-1){
upd1(lf[c],1);
}
}
continue;
}
if(p[t].first=='Q'){
d=p[t].second.first;c=p[t].second.second;
E=0;
lc=lca(c,d);
UP1(d);UP2(c);
if(c!=lc&&d!=lc){
C=upto(c,lc);D=upto(d,lc);
if(f[C]==-1||f[D]==-1||f[C]>f[D]) E=1;
}
if(E==0){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
continue;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
7744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
7744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
7752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
7752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
7804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
7804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
7904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
7904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
261 ms |
7704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
261 ms |
7704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
262 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
262 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
