Description
量子力学指出，宇宙并非只有一种形态。
根据量子理论，一件事件发生之后可以产生不同的后果，而所有可能的后果都会形成自己的宇宙。
我们可以把一个宇宙看成一个时间轴，虫洞可以看成不同宇宙的不同时间之间的跳跃。虫洞非常的不稳定，存在时间只有一瞬间。
如果存在虫洞事件(U1,t1,U2,t2)那么在宇宙U1的t1时间和宇宙U2的t2时间会被连接，此时就会发生时空跳跃现象。
你可以认为：同一个宇宙同一个时刻最多只存在一个虫洞事件。
为了研究虫洞的性质，科学家向宇宙深处发射了虫洞探测器。
该探测器会检测到自己存在的宇宙中的虫洞事件，并且一旦检测到虫洞事件就一定会进行跳跃。
由于科学家并不确定虫洞事件的具体位置时间，所以暂时用电脑模拟很多平行宇宙以及虫洞事件。
你将被告之探测器被放出时所在的宇宙名称和时间。
你需要处理以下信息：
1. “ADD U1 t1 U2 t2” 表示在模拟中加入一个虫洞事件(U1,t1,U2,t2),其中U1和U2是字符串，t1和t2是32位非负整数
2. “DEL U1 t1 U2 t2” 表示删除之前加入过的一个虫洞事件，保证该事件之前被ADD过。
3. “QUERY” 表示询问探测器经过足够久的时间后会落入哪个宇宙，输出宇宙名称。如果答案不确定，请输出“*”
Input
第一行: U0 t0 表示探测器发射的地点和时间。保证该时刻不存在虫洞事件。
第二行： 正整数 Q 表示操作数
接下来 Q 行: 2种操作，如描述，ADD或ASK。无多余字符。
Output
按照输入顺序，回答每一个ASK操作，直接输出宇宙名称或者“*”，每个回答占一行。
将每个有事件的时刻建一个点表示，每个点有且只有一个后继，构成基环内向树森林，查询就是查环上是否同色，如果是的话输出颜色，可用lct维护
#include<bits/stdc++.h> int _(){ int x=0,f=1,c=getchar(); while(c<48)c=='-'?f=-1:0,c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x*f; } void _(char*s){ scanf("%s",s); } char ss[1007][23],s[23]; int nx[21111][27],ptr=1,st1,st2,idp=0,qs[210007][5],qp,ids[1007]; std::vector<int>e[1007]; struct node{ node*c[2],*f,*ff; int id,ida; bool nrt(){return this==f->c[0]||this==f->c[1];} void up(); }ns[410007],*nil=ns; void node::up(){ ida=(c[0]!=nil&&c[0]->ida!=id||c[1]!=nil&&c[1]->ida!=id)?0:id; } void rot(node*w){ node*f=w->f,*g=f->f; int d=f->c[1]==w; if(f->nrt())g->c[g->c[1]==f]=w; w->f=g; (f->c[d]=w->c[d^1])->f=f; (w->c[d^1]=f)->f=w; f->up(); } void sp(node*w){ while(w->nrt()){ node*f=w->f; if(f->nrt())rot((w==f->c[0])==(f==f->f->c[0])?f:w); rot(w); } w->up(); } node*acs(node*x){ node*y=nil; for(;x!=nil;sp(x),x->c[1]=y,x->up(),y=x,x=x->f); return y; } node*gl(node*w){ while(w->c[0]!=nil)w=w->c[0]; sp(w); return w; } node*grt(node*w){ node*w0=w; while(w->f!=nil)w=w->f; sp(w0); return w; } void lk(node*x,node*y){ node*w=acs(x); if(grt(y)==w)x->ff=y; else sp(x),x->f=y; } node*ct(node*x){ acs(x),sp(x); node*y=x->c[0]; if(y!=nil){ x->c[0]=y->f=nil; x->up(); y=gl(acs(y)); if(y->ff!=nil&&grt(y->ff)==x){ y->f=y->ff; y->ff=nil; } }else x->ff=nil; } int tins(){ int w=1; for(int i=0;s[i];++i){ int c=s[i]-'a'; if(!nx[w][c])nx[w][c]=++ptr; w=nx[w][c]; } if(!nx[w][26]){ nx[w][26]=++idp; strcpy(ss[idp],s); } return nx[w][26]; } int gid(int a,int b){ return ids[a]+std::lower_bound(e[a].data(),e[a].data()+e[a].size(),b)-e[a].data(); } int main(){ _(s); e[st1=tins()].push_back(st2=_()); qp=_(); for(int i=0;i<qp;++i){ _(s); if(s[0]=='Q'){ qs[i][0]=0; }else{ qs[i][0]=s[0]=='A'?1:2; _(s); qs[i][1]=tins(); qs[i][2]=_(); _(s); qs[i][3]=tins(); qs[i][4]=_(); if(qs[i][0]==1){ e[qs[i][1]].push_back(qs[i][2]); e[qs[i][3]].push_back(qs[i][4]); } } } ids[1]=1; ns[0]=(node){nil,nil,nil,nil,0,0}; for(int i=1;i<=idp;++i){ int*l=e[i].data(),*r=l+e[i].size(); std::sort(l,r); e[i].resize(std::unique(l,r)-l); int mx=ids[i+1]=ids[i]+e[i].size()+1; for(int j=ids[i];j<mx;++j)ns[j]=(node){nil,nil,ns+j+1,nil,i,i}; ns[mx-1].f=nil; ns[mx-1].ff=ns+mx-1; } st2=gid(st1,st2); ss[0][0]='*'; for(int i=0;i<qp;++i){ if(qs[i][0]==0){ node*w=gl(acs(ns+st2)); puts(ss[acs(w->ff)->ida]); }else{ int w1=gid(qs[i][1],qs[i][2]); int w2=gid(qs[i][3],qs[i][4]); ct(ns+w1),ct(ns+w2); if(qs[i][0]==1){ lk(ns+w1,ns+w2+1); lk(ns+w2,ns+w1+1); }else{ lk(ns+w1,ns+w1+1); lk(ns+w2,ns+w2+1); } } } return 0; }