思路同第一篇题解

#include<bits/stdc++.h>
using namespace std;
const int N=30005,M=100005;
int n,m,cnt=0,sum=0;
int u[N],v[N],f[N],dep[N],siz[N],mson[N],top[N];
int ans[M],idx[N],op[M];
vector<int> to[N];
bool book[N],ca[N][N];
struct edge{
	int l,r,val,tp,laz;
}t[N*4];
void spread(int p){
	if(!t[p].laz)return;
	t[p*2].laz=t[p*2+1].laz=1;
	t[p].laz=0;
	t[p*2].val=t[p*2+1].val=0;
	t[p*2].tp=t[p*2+1].tp=0;
}
void dfs1(int x,int fa){
	book[x]=1;
	f[x]=fa;
	siz[x]=1;
	dep[x]=dep[fa]+1;
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(book[y]||ca[x][y])continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[mson[x]]){
			mson[x]=y;
		}
	}
}
void dfs2(int x,int topx){
	idx[x]=++sum;
	book[x]=1;
	top[x]=topx;
	if(mson[x])dfs2(mson[x],topx);
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(book[y]||ca[x][y])continue;
		dfs2(y,y);
	}
}
void build(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	if(l==r){
		if(l!=1)t[p].val=1;
		return;
	}int mid=(t[p].l+t[p].r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].val=t[p*2].val+t[p*2+1].val;
}
void change(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].val=0;
		t[p].tp=0;
		t[p].laz=1;
		return;
	}spread(p);
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid)change(p*2,l,r);
	if(r>mid)change(p*2+1,l,r);
	t[p].val=t[p*2].val+t[p*2+1].val;
}
int query(int p,int l,int r){
	spread(p);
	if(t[p].l>=l&&t[p].r<=r){
		return t[p].val;
	}int mid=(t[p].l+t[p].r)/2;
	int res=0;
	if(l<=mid)res+=query(p*2,l,r);
	if(r>mid)res+=query(p*2+1,l,r);
	return res;
}
void cha(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		change(1,idx[top[x]],idx[x]);
		x=f[top[x]];
	}if(dep[x]<dep[y])swap(x,y);
	int yy;
	for(int i=0;i<to[y].size();i++){
		if(top[to[y][i]]==top[x]&&to[y][i]!=f[y]){
			yy=to[y][i];
			break;
		}
	}
	change(1,idx[yy],idx[x]);
}
int ask(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
	//	printf("%d %d\n",x,y);
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res+=query(1,idx[top[x]],idx[x]);
		x=f[top[x]];
	}if(dep[x]<dep[y])swap(x,y);
	int yy;
	for(int i=0;i<to[y].size();i++){
		if(top[to[y][i]]==top[x]&&to[y][i]!=f[y]){
			yy=to[y][i];
			break;
		}
	}
	res+=query(1,idx[yy],idx[x]);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	while(1){
		cnt++;
		scanf("%d",&op[cnt]);
		if(op[cnt]==-1)break;
		scanf("%d%d",&u[cnt],&v[cnt]);
		if(op[cnt]==0){
			ca[u[cnt]][v[cnt]]=1;
			ca[v[cnt]][u[cnt]]=1;
		}
	}cnt--;
	dfs1(1,0);
	memset(book,0,sizeof(book));
	dfs2(1,1);
	for(int i=cnt;i>=1;i--){
		if(op[i]==1){
			ans[i]=ask(u[i],v[i]);
		}else{
			cha(u[i],v[i]);
		}
	}for(int i=1;i<=cnt;i++){
		if(op[i]==0)continue;
		printf("%d\n",ans[i]);
	}
	return 0; 
}