因为只能支持加入一个边维护边双，所以时光倒流
维护好边双，每次就是提取出(x,y)的链，答案就是链长度-1
具体维护边双的话，
void access(int x){
for(reg y=0;x;y=x,x=t[y].fa=fin(t[x].fa)){//注意更新
splay(x);rs=y;pushup(x);
}
}
dele(int x,int y)把x节点的father指向y，这个x临死前把信息指到y，以便于后面要找x的直接找y即可。{
if(x) fa[x]=y,dele(rs,y),dele(ls,y)
}
merge函数(int x,int y){
if(x==y（在一起）)return 什么都不用做
makert(x)
if(findrt(y)!=x){
t[x].fa=y相当于直接link
return;
}
splay(x)
出环了。那么要缩点，x现在是根，并且作为代表点
dele(rs,x)
t[x].ch[1]=0,干掉子树，这个子树已经名存实亡了。
pushup(x)
}
我通过merge，dele函数打上标记，
在access的时候把标记依次还原，达到真正缩点的目的。
而并查集使我每次都会到真正的节点。不会到已经删除的节点。
代码：
#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') #define ls t[x].ch[0] #define rs t[x].ch[1] using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=30000+5; const int M=100000+5; int n,m; struct node{ int sz,fa,ch[2],r; }t[N]; int fa[N]; int fin(int x){ return fa[x]==x?x:fa[x]=fin(fa[x]); } bool nrt(int x){ return (t[t[x].fa].ch[0]==x)||(t[t[x].fa].ch[1]==x); } void rev(int x){ swap(t[x].ch[0],t[x].ch[1]); t[x].r^=1; } void pushdown(int x){ if(t[x].r){ t[x].r=0; rev(ls);rev(rs); } } void pushup(int x){ t[x].sz=t[ls].sz+t[rs].sz+1; } void rotate(int x){ int y=t[x].fa,d=t[y].ch[1]==x; t[t[y].ch[d]=t[x].ch[!d]].fa=y; if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x; else t[x].fa=t[y].fa; t[t[y].fa=x].ch[!d]=y; pushup(y); } int sta[N]; void splay(int x){ int y=x,z=0; sta[++z]=y; while(nrt(y)) y=t[y].fa,sta[++z]=y; while(z) pushdown(sta[z--]); while(nrt(x)){ y=t[x].fa,z=t[y].fa; if(nrt(y)){ rotate(((t[y].ch[0]==x)==(t[z].ch[0]==y))?y:x); } rotate(x); } pushup(x); } void access(int x){ for(reg y=0;x;y=x,x=t[y].fa=fin(t[x].fa)){ splay(x);rs=y;pushup(x); } } void makert(int x){ access(x);splay(x);rev(x); } int findrt(int x){ access(x);splay(x); pushdown(x); while(t[x].ch[0]) pushdown(x=t[x].ch[0]); splay(x); return x; } void dele(int x,int y){ if(x) fa[x]=y,dele(ls,y),dele(rs,y); } void merge(int x,int y){ if(x==y) return; makert(x); if(findrt(y)!=x){ t[x].fa=y; pushup(y); return; } dele(t[x].ch[1],x); t[x].ch[1]=0; pushup(x); } void split(int x,int y){ makert(x);access(y);splay(y); } struct edge{ int x,y; bool friend operator <(edge a,edge b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; } }e[M]; bool vis[M]; struct que{ int c; int x,y; }q[M]; int ans[M],cnt; int main(){ rd(n);rd(m); int x,y; for(reg i=1;i<=n;++i){ fa[i]=i;t[i].sz=1; } for(reg i=1;i<=m;++i){ rd(x);rd(y); if(x>y) swap(x,y); e[i].x=x;e[i].y=y; } sort(e+1,e+m+1); int c; int tot=0; while(1){ rd(c); if(c==-1) break; ++tot; rd(x);rd(y); if(x>y) swap(x,y); if(c==0){ edge lp;lp.x=x,lp.y=y; vis[lower_bound(e+1,e+m+1,lp)-e]=1; } q[tot].x=x,q[tot].y=y; q[tot].c=c; } for(reg i=1;i<=m;++i){ if(!vis[i]){ x=fin(e[i].x),y=fin(e[i].y); merge(x,y); } } for(reg i=tot;i>=1;--i){ x=fin(q[i].x);y=fin(q[i].y); if(q[i].c==1){ ++cnt; split(x,y); ans[cnt]=t[y].sz-1; } else{ merge(x,y); } } for(reg i=cnt;i>=1;--i){ printf("%d ",ans[i]); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/19 9:57:28 */