#include #include #include #include #define N 1500010using namespace std;int fa[N],n,m,Q,c[N][2],f[N],mx[N],st[N],v[N],tot(0),ans[100010],rev[N];struct use{int st,en,id,w,d;}e[N];struct use2{int f,x,y,d;}q[100010];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int getf(int x){if (x!=f[x]) f[x]=getf(f[x]);return f[x];}inline bool cmp(use a,use b){return a.w v[mx[x]]) mx[x]=mx[l]; if (v[mx[r]]>v[mx[x]]) mx[x]=mx[r]; }inline void pushdown(int x){ int l=c[x][0],r=c[x][1]; if(rev[x]){ rev[x]^=1;rev[l]^=1;rev[r]^=1; swap(c[x][0],c[x][1]); } }inline void rotata(int x){ int y=fa[x],z=fa[y],l,r; if (c[y][0]==x) l=0;else l=1;r=l^1; if (!isroot(y)){if (c[z][0]==y)c[z][0]=x;else c[z][1]=x;} fa[x]=z;fa[c[x][r]]=y;fa[y]=x; c[y][l]=c[x][r];c[x][r]=y; updata(y);updata(x);}inline void splay(int x){ int top(0);st[++top]=x; for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; for (int i=top;i;i--) pushdown(st[i]); while (!isroot(x)){ int y=fa[x],z=fa[y]; if(!isroot(y)){if (c[y][0]==x^c[z][0]==y) rotata(y);else rotata(x);} rotata(x); }}inline void access(int x){int t(0);while (x){splay(x);c[x][1]=t;t=x;updata(x);x=fa[x];}}inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}inline void link(int x,int y){makeroot(x);fa[x]=y;}inline void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;}inline void split(int x,int y){makeroot(y);access(x);splay(x);}inline int query(int x,int y){split(x,y);return mx[x];}inline int find(int x,int y){ int l=1,r=m; while (l<=r){ int mid=(l+r)>>1; if (e[mid].st e[i].en) swap(e[i].st,e[i].en); } sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++){e[i].id=i;v[i+n]=e[i].w;mx[i+n]=i+n;} sort(e+1,e+m+1,cmp2); for (int i=1;i<=Q;i++){ q[i].f=read();q[i].x=read();q[i].y=read(); if (q[i].x>q[i].y) swap(q[i].x,q[i].y); if (q[i].f==2){int t=find(q[i].x,q[i].y);q[i].d=e[t].id;e[t].d=1;} } sort(e+1,e+m+1,cmp3); for (int i=1;i<=m;i++) if (!e[i].d){ int r1=getf(e[i].st),r2=getf(e[i].en); if (r1!=r2){f[r1]=r2;link(e[i].st,i+n);link(e[i].en,i+n);tot++;} if (tot==n-1) break; } for (int i=Q;i>=1;i--){ if (q[i].f==1) ans[++ans[0]]=v[query(q[i].x,q[i].y)]; else{ int t=query(q[i].x,q[i].y); if (e[q[i].d].w
转载地址：https://blog.csdn.net/sunshinezff/article/details/50977349 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
