#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));
#define mod 1000000007
inline int add(int a,int b){
int r=a+b;
while(r>=mod)r-=mod;
while(r<0)r+=mod;
return r;
}
inline int mult(int a,int b){
return (int)(((ll)(a*b))%mod);
}
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
struct node{
int s,e,m,v,lz;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1,v=0,lz=0;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
v+=lz;
if(s!=e)l->lz+=lz,r->lz+=lz;
lz=0;
}
void up(int x,int y,int nv){
if(s==x&&e==y){lz+=nv;return;}
if(y<=m)l->up(x,y,nv);
else if(x>m)r->up(x,y,nv);
else l->up(x,m,nv),r->up(m+1,y,nv);
l->ppo(),r->ppo();
v=l->v+r->v;
}
int qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return l->qry(x,m)+r->qry(m+1,y);
}
}*rt;
#define maxn 120005
int n,k,p[20][maxn],pwt[maxn],asc[maxn],des[maxn],dep[maxn],ans[maxn],pre[maxn],pst[maxn],cnt=1;
vii AL[maxn];
vi cqry[maxn],rem[maxn];
vii qqry[maxn],qrys[maxn];
void dfs(int u,int par){
pre[u]=cnt++;
for(auto[v,w]:AL[u]){
if(v==par)continue;
p[0][v]=u;
if(pwt[u]==-1)asc[v]=des[v]=1;
else if(w<pwt[u])asc[v]=asc[u]+1,des[v]=des[u];
else asc[v]=asc[u],des[v]=des[u]+1;
dep[v]=dep[u]+1;
pwt[v]=w;
dfs(v,u);
}
pst[u]=cnt-1;
}
int fpar(int x,int k){
for(int i=19;i>=0;--i){
if((1<<i)<=k)x=p[i][x],k-=(1<<i);
}
return x;
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int k=19;k>=0;--k){
if(p[k][a]!=-1&&dep[p[k][a]]>=dep[b])a=p[k][a];
}
if(a==b)return a;
for(int k=19;k>=0;--k){
if(p[k][a]!=p[k][b])a=p[k][a],b=p[k][b];
}
return p[0][a];
}
void dfs2(int u,int p){
//pf("dfs2: %d %d\n",u,p);
for(auto[t,m]:qrys[u]){
//pf("qry: %d %d\n",t,m);
ans[t]+=rt->qry(0,t)*m;
}
for(auto [v,w]:AL[u]){
if(v==p)continue;
//pf("up: %d 1\n",w);
rt->up(w,w,1);
dfs2(v,u);
}
//for(int t:rem[u])pf("up: %d -1\n",t),rt->up(t,t,-1);
}
int main(){
//freopen("servers_3.in","r",stdin);
sf("%d%d",&n,&k);
for(int i=0;i<n+k-1;++i){
char c;sf(" %c",&c);
if(c=='S'){
int a,b;sf("%d%d",&a,&b);
AL[a].pb({b,i});
AL[b].pb({a,i});
ans[i]=-3;
}
else if(c=='Q'){
int a,b;sf("%d%d",&a,&b);
qqry[b].pb({a,i});
}
else{
int a;sf("%d",&a);
cqry[a].pb(i);
}
}
for(int i=1;i<=n;++i)sort(all(AL[i]),[](ii &a,ii &b){return a.se>b.se;});
p[0][1]=-1;
asc[1]=des[1]=0;
pwt[1]=-1;
dfs(1,0);
#ifdef DEBUG
for(int i=1;i<=n;++i){
pf("%d: asc %d, dec %d\n",i,asc[i],des[i]);
}
#endif
for(int k=0;k<19;++k){
for(int i=1;i<=n;++i){
if(p[k][i]!=-1)p[k+1][i]=p[k][p[k][i]];
else p[k+1][i]=-1;
}
}
//x --asc--> u --w1--> lca
//y --w3--> smt --dec--> v --w2--> lca
//w1 < w2
//w3 < t
for(int x=1;x<=n;++x){
for(auto[y,t]:qqry[x]){
if(x==y){
ans[t]=-1;
continue;
}
int l=lca(x,y);
if(l==y){
int jmp=dep[x]-dep[y];
if(asc[x]>=jmp&&pwt[fpar(x,jmp-1)]<t)ans[t]=-1;
else ans[t]=-2;
}
else if(l==x){
int jmp=dep[y]-dep[x];
if(des[y]>=jmp&&pwt[y]<t)ans[t]=-1;
else ans[t]=-2;
}
else{
int jmpx=dep[x]-dep[l],jmpy=dep[y]-dep[l];
if(asc[x]<jmpx||des[y]<jmpy)ans[t]=-2;
else if(pwt[fpar(x,jmpx-1)]>=pwt[fpar(y,jmpy-1)])ans[t]=-2;
else if(pwt[y]>t)ans[t]=-2;
else ans[t]=-1;
}
}
}
//answer c queries going down first
vector<iii> queries;
for(int i=1;i<=n;++i){
if(i!=1)queries.pb({pwt[i],i,0});//update
for(int t:cqry[i])queries.pb({t,i,1});//query
}
sort(all(queries));
rt=new node(1,n);
for(auto [t,i,type]:queries){
if(type==0){
if(i!=1){
int par=p[0][i];
rt->up(pre[par],pre[par],1);
}
int lim=fpar(i,des[i]);
if(lim!=1){
lim=p[0][lim];
rt->up(pre[lim],pre[lim],-1);
}
}
else{
ans[t]+=rt->qry(pre[i],pst[i]);
}
}
for(int i=1;i<=n;++i){
for(int t:cqry[i]){
qrys[i].pb({t,1});
int lim=fpar(i,asc[i]),lim2=fpar(i,des[i]);
if(i!=1)rem[lim2].pb(pwt[i]);
qrys[lim].pb({t,-1});
}
}
//pf("rt: %d\n",n+k);
rt=new node(0,n+k);
dfs2(1,-1);
for(int i=0;i<n+k-1;++i){
if(ans[i]==-1)pf("yes\n");
else if(ans[i]==-2)pf("no\n");
else if(ans[i]!=-3)pf("%d\n",ans[i]+1);
}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
6 9
S 1 2
S 1 3
S 3 4
S 4 5
S 1 6
Q 2 1
Q 3 1
Q 4 1
Q 5 1
Q 6 1
Q 1 2
Q 3 2
Q 4 2
Q 5 2
Q 6 2
find preorder/postorder
segment tree
make into offline queries
*/
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:150:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | sf("%d%d",&n,&k);
| ^
servers.cpp:152:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | char c;sf(" %c",&c);
| ^
servers.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | int a,b;sf("%d%d",&a,&b);
| ^
servers.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | int a,b;sf("%d%d",&a,&b);
| ^
servers.cpp:164:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | int a;sf("%d",&a);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
28876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
28876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
28912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
28912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
56 ms |
28872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
56 ms |
28872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
28844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
28844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
54 ms |
28808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
54 ms |
28808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
28908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
28908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
