一点也不优雅的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\n",lastans=0); else{ makeroot(u);access(t+v);splay(t+v); printf("%d\n",lastans=t[v].Max); } } } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/6893409.html
相关资源：数据结构—成绩单生成器