首页 > 代码库 > BZOJ 4668 LCT
BZOJ 4668 LCT
思路:
这不是LCT裸题嘛23333
(好像并查集+按秩合并就可以搞了 我还是too young)
维护边权的话 就新加一个点 代表边 这个点想线段的两个端点连边就好了
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=1000050;int n,m,op,xx,yy,top,lastans,T;int fa[N],ch[N][2],q[N],maxx[N],rev[N],v[N],f[N];bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}void push_up(int x){maxx[x]=max(v[x],max(maxx[ch[x][0]],maxx[ch[x][1]]));}void push_down(int x){if(rev[x])rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,rev[x]=0,swap(ch[x][0],ch[x][1]);}void rotate(int p){ int q=fa[p],y=fa[q],x=(ch[q][1]==p); ch[q][x]=ch[p][!x],fa[ch[q][x]]=q; ch[p][!x]=q,fa[p]=y; if(!isroot(q)){ if(ch[y][0]==q)ch[y][0]=p; if(ch[y][1]==q)ch[y][1]=p; }fa[q]=p,push_up(q);}void splay(int x){ q[++top]=x; for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i]; while(top)push_down(q[top]),top--; for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])if(!isroot(y)){ if((ch[y][0]==x)^(ch[fa[y]][0]==y))rotate(x); else rotate(y); }push_up(x);}void access(int x){for(int t=0;x;t=x,x=fa[x])splay(x),ch[x][1]=t,push_up(x);}void makeroot(int x){access(x),splay(x),rev[x]^=1;}void link(int x,int y){makeroot(x),fa[x]=y;}void split(int x,int y){makeroot(x),access(y),splay(y);}int find(int x){return x==f[x]?x:f[x]=find(f[x]);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++){ scanf("%d%d%d",&op,&xx,&yy); xx^=lastans,yy^=lastans; if(op){ int fx=find(xx),fy=find(yy); if(fx!=fy)printf("%d\n",lastans=0); else split(xx,yy),printf("%d\n",lastans=maxx[yy]); } else{ T++; int fx=find(xx),fy=find(yy); if(fx!=fy){ f[fx]=fy,v[n+T]=maxx[n+T]=T; link(xx,n+T),link(n+T,yy); } } }}
BZOJ 4668 LCT
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。