C++11(clang++ 3.9) 解法, 执行用时: 332ms, 内存消耗: 13688K, 提交时间: 2019-11-10 11:58:04

#include<bits/stdc++.h>
using namespace std;
#define ls x << 1
#define rs x << 1 | 1
const int N = 30005;
const int M = 100005;
int head[M << 1] , Next[M<<1] , tot ,  ver[M<<1];
int ok[M<<1];
int n  , m;
map<int , int>mp;
int top[N] , id[N] ,cnt;
void add(int x ,int y){
	ver[++tot] = y;
	Next[tot] = head[x];
	head[x] = tot;
    mp[x*(n+1)+y] = tot;
}
int fa[N] , d[N] , size[N] , son[N];
void dfs1(int x ,int  f ,int deep){
	fa[x] = f;
	d[x] = deep;  
	size[x] = 1;
	for(int i = head[x] ; i ; i = Next[i]){
		int y = ver[i];
		if(y == f || ok[i] || size[y])continue;
		dfs1(y , x , deep + 1);
		size[x] += size[y];
		if(size[y] > size[son[x]]){
			son[x] = y;
		}
	}
}
void dfs2(int x ,int topf){
	id[x] = ++cnt;
	top[x] = topf;
	if(!son[x])return ;
	dfs2(son[x] , topf);
	for(int i = head[x] ; i ; i = Next[i]){
		int y = ver[i];
		if(y == son[x] || y == fa[x] || ok[i] || fa[y] != x)continue;
		dfs2(y , y);
	}
}
int sm[N << 2] , lz[N << 2];
void pushdown(int x){
	if(lz[x]){
	sm[x] = sm[ls] = sm[rs] = 0;
	lz[ls] = lz[rs] = 1;
	lz[x] = 0;
	return ;
	}
	return ;
}
void pushup(int x){
	sm[x] = sm[ls] + sm[rs];
    return ;
}
void build(int x ,int l, int r){
	if(l == r){
		sm[x] = 1;
	    return ;
	}
	int mid = (l + r) >> 1;
    build(ls , l , mid);
    build(rs , mid + 1, r);
    pushup(x);
}
int skad;
void change(int x , int l ,int r ,int L , int R){
	if(L > r || R < l)return;
	if(L <= l && r <=  R){
		sm[x] = 0;
		lz[x] = 1;
	  return;
	}
	pushdown(x);
	int mid = (l + r ) >> 1;
	change(ls , l , mid , L , R);
	change(rs , mid + 1, r , L ,R);
	pushup(x);
}
int query(int x ,int l ,int r ,int L , int R){
	if(L > r || R < l)return 0;
	if(L <= l && r <= R){
		return sm[x];
	}
	pushdown(x);
	int mid = (l + r)>> 1;
	pushup(x);
	return query(ls , l , mid , L , R) + query(rs , mid + 1 , r , L ,R);
} 
void Qchange(int x ,int y){
	while(top[x] != top[y]){
		if(d[top[x]] < d[top[y]])swap(x , y);
		change(1 , 1 , n , id[top[x]],id[x]);
		x = fa[top[x]];
	}
	if(d[x] < d[y]){
		swap(x , y);
	}
	if(d[x] != d[y]){
		change(1 , 1 , n , id[y] + 1 , id[x]);
	}
}
void dfs3(int x){
	for(int i= head[x] ; i ; i = Next[i]){
		int  y = ver[i];
		if(ok[i]){
		continue;	
		}
		if(fa[y] == x){
			dfs3(y);
		}
		if(fa[x] != y && d[y] < d[x]){
			Qchange(y , x);
		}
	}
}
int Qquery(int x ,int y){
	int ans = 0;
	while(top[x] != top[y]){
		if(d[top[x]] < d[top[y]])swap(x , y);
		ans += query(1 , 1 , n , id[top[x]],id[x]);
		x = fa[top[x]];
	}
	if(d[x]<d[y])
        swap(x,y);
		ans += query(1 , 1, n , id[y] + 1 , id[x]);
		return ans;	
}
int que[N][5];
int fin[40005];
int main () {
	cin >> n >> m;
	for(int i = 1;i <= m ; i ++){
		int x , y;
		scanf("%d%d" , &x , &y);
		add(x , y);
		add(y , x);
	}
	int pos = 0;
	while(1){
		int a;
		scanf("%d" , &a);
		if(a == -1)break;
		int b , c;
		scanf("%d%d" , &b , &c);
		que[++pos][1] = a;
		que[pos][2] = b;
		que[pos][3] = c;
		if(a == 0){
			ok[mp[b*(n+1)+c]] = ok[mp[c*(n+1)+b]] = 1;
		}
	}
	dfs1(1 , 0 , 1);
	dfs2(1 , 1);
	build(1 , 1 , n);
	dfs3(1);
	for(int i = pos ; i ; i --){
		if(que[i][1]){
		fin[i] = Qquery(que[i][2] , que[i][3]); 
		}else{
			Qchange(que[i][2] , que[i][3]);
		}
	}
	for(int i = 1;i <= pos ;i ++){
		if(que[i][1] != 1)continue;
			cout << fin[i] << endl;
	}
	return 0;
}