10分提交记录

好像都错在很后面……

#include <map>
#include <cstdio>
#define debug puts("poor shik!");
const int maxn = 30005;
inline void swap(int &a,int &b) {
	a ^= b,b ^= a,a ^= b;
}
int n,m;
struct Union_Set {
	int fa[maxn];
	inline int getfa(int x) {
		return fa[x] == x ? x : fa[x] = getfa(fa[x]);
	}
} tre,lct;
int fa[maxn],ch[maxn][2],rev[maxn],siz[maxn];
inline void pushup(int x) {
	siz[x] = 1+siz[ch[x][0]]+siz[ch[x][1]];
}
inline void grev(int x) {
	rev[x] ^= 1,swap(ch[x][0],ch[x][1]);
}
inline void pushdown(int x) {
	if(rev[x])rev[x] = 0,grev(ch[x][0]),grev(ch[x][1]);
}
inline void connect(int x,int F,int sid) {
	ch[F][sid] = x,fa[x] = F;
}
inline int identify(int x) {
	return ch[fa[x]][1] == x;
}
inline int nroot(int x) {
	return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
inline void rotate(int x) {
	int y=fa[x],z=fa[y],xy=identify(x),yz=identify(y),nry=nroot(y);
	connect(ch[x][xy^1],y,xy),connect(y,x,xy^1),fa[x] = z;
	if(nry)ch[z][yz] = x;
	pushup(y),pushup(x);
}
inline void pushtag(int x) {
	if(nroot(x))pushtag(fa[x]);
	pushdown(x);
}
inline void Splay(int x) {
	pushtag(x);
	while(nroot(x)) {
		int y=fa[x];
		if(nroot(y))identify(x)^identify(y)?rotate(x):rotate(y);
		rotate(x);
	}
}
inline void access(int x) {
	for(int y=0; x; y=x,x=fa[x]=lct.getfa(fa[x]))Splay(x),ch[x][1] = y,pushup(x);
}
inline void evert(int x) {
	access(x),Splay(x),grev(x);
}
inline void split(int x,int y) {
	evert(x),access(y),Splay(y);
}
inline void link(int x,int y) {
	evert(x),fa[x]=y;
}
inline void reset(int now,int root) {
	lct.fa[now] = root;
//	printf("reset:%d %d\n",now,root);
	if(ch[now][0])reset(ch[now][0],root);
	if(ch[now][1])reset(ch[now][1],root);
}
int did[maxn*10];
struct OP {
	int ty,eid,x,y;
} p[maxn];
struct E {
	int x,y;
	bool operator <(E b)const {
		return x<b.x;
	}
} e[maxn*10];
std :: map<E,int> idd;
int type,x,y,cnt;
inline void inedge(int iddd) {
	int fx = tre.getfa(e[iddd].x),fy = tre.getfa(e[iddd].y),X,Y;
	X = lct.getfa(e[iddd].x);
	Y = lct.getfa(e[iddd].y);
	if(fx != fy) {
		tre.fa[fx] = fy;
		link(X,Y);
		return ;
	}
//	printf("inedge:%d %d %d %d %d\n",iddd,e[iddd].x,e[iddd].y,X,Y);
	split(X,Y);
	reset(Y,Y);
	ch[Y][0] = 0,siz[Y] = 1;
}
int ans[maxn],anscnt;
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; ++i)lct.fa[i] = tre.fa[i] = i,siz[i] = 1;
	for(int i=1; i<=m; ++i){
		scanf("%d %d",&e[i].x,&e[i].y);
		if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
		idd[(E) {e[i].x,e[i].y}] = i;
	}
	while(scanf("%d",&type),type!=-1) {
		scanf("%d %d",&x,&y);
		if(x>y)swap(x,y);
		if(type == 0)p[++cnt].ty = type,p[cnt].eid = idd[(E) {x,y}],did[idd[(E) {x,y}]] = 1;
		else p[++cnt].ty = type,p[cnt].x = x,p[cnt].y = y;
	}
	for(int i=1; i<=m; ++i)if(!did[i])inedge(i);
	for(int i=cnt;i;--i){
		if(p[i].ty == 0)inedge(p[i].eid);
		if(p[i].ty == 1)p[i].x=lct.getfa(p[i].x),p[i].y=lct.getfa(p[i].y),split(p[i].x,p[i].y),ans[++anscnt] = siz[p[i].y]-1;
	}
	for(int i=anscnt;i;--i)printf("%d\n",ans[i]);
	return 0;
}

求救，蒟蒻又调2h了……