一点也不优雅的LCT大力跑过去了23333.标算是并查集加特技...
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500005;
struct node{
node* ch[2],*prt;
bool mk,isroot;
int val,Max;
void rev(){
swap(ch[0],ch[1]);mk^=1;
}
void pd(){
if(mk){
mk=0;
if(ch[0])ch[0]->rev();
if(ch[1])ch[1]->rev();
}
}
void upd(){
Max=val;
if(ch[0])Max=max(Max,ch[0]->Max);
if(ch[1])Max=max(Max,ch[1]->Max);
}
}t[maxn*2];
inline int isch1(node* rt){return rt==rt->prt->ch[1];}
void rot(node* rt,int t){
node* p=rt->prt,*c=rt->ch[t];
c->pd();
if(rt->isroot)rt->isroot=false,c->isroot=true;
else p->ch[isch1(rt)]=c;
c->prt=p;
rt->ch[t]=c->ch[t^1];if(c->ch[t^1])c->ch[t^1]->prt=rt;
c->ch[t^1]=rt;rt->prt=c;
rt->upd();c->upd();
}
void splay(node* rt){
node* p,* g;
while(!rt->isroot){
p=rt->prt;
if(p->isroot){
p->pd();
rot(p,isch1(rt));
}else{
g=p->prt;g->pd();p->pd();
int t1=isch1(rt),t2=isch1(p);
if(t1==t2){
rot(g,t2);rot(p,t1);
}else{
rot(p,t1);rot(g,t2);
}
}
}
rt->pd();
}
void access(node* rt){
node* last=0;
while(rt){
splay(rt);
if(rt->ch[1]){
rt->ch[1]->isroot=true;
}
rt->ch[1]=last;
if(last)last->prt=rt,last->isroot=false;
rt->upd();
last=rt;rt=rt->prt;
}
}
int findroot(int x){
node* p=t+x;
access(p);splay(p);
while(p->ch[0])p=p->ch[0];
return p-t;
}
void makeroot(int x){
access(t+x);splay(t+x);t[x].rev();
}
void link(int u,int v){
makeroot(u);t[u].prt=(t+v);
}
int lastans=0;
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)t[i].isroot=true,t[i].val=t[i].Max=0;
int typ,u,v;
int cntedge=0;
while(m--){
scanf("%d%d%d",&typ,&u,&v);
u^=lastans;v^=lastans;
if(typ==0){
++cntedge;
if(findroot(u)!=findroot(v)){
t[n+cntedge].isroot=true;t[n+cntedge].Max=t[n+cntedge].val=cntedge;
link(u,n+cntedge);link(n+cntedge,v);
}
}else{
if(findroot(u)!=findroot(v))printf("%d
",lastans=0);
else{
makeroot(u);access(t+v);splay(t+v);
printf("%d
",lastans=t[v].Max);
}
}
}
return 0;
}