题意
给出一个无向图，有下列操作：
- $(1,a,b)$ ，查询 $a\rightarrow b$ 路径上桥的数量
- $(0,a,b)$ ，删除边 $(a,b)$ 。
保证无论航线如何被破坏，任意时刻任意两点都能够相互到达。
其中点数 $N\le 30000$ ，边数 $M\le 100000$ ，操作数 $Q\le 40000$ 。
题解
显然，桥的数量就是缩完点后两点间的树上距离，动态询问树上距离显然就是树剖了。
对于操作 $2$ ，可以通过离线逆向处理成加边操作。
在一棵树上，如果给没有边的两点加上了边，那就构成了环，相当于原先的桥都被取消掉了。可以通过把两点间边权修改为 $0$ 来实现。
对于样例：
5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1
最初的状态 $(4,2)$ 是断开了的。所以 $5\rightarrow 1$ 距离显然是 $3$ 。
加上 $(4,2)$ 后就成环了，所以把 $4\rightarrow 2$ 距离消成 $0$ 。那么 $1\rightarrow 5$ 距离就只是 $1$ 了。
但显然最后的状态不一定是树，那么直接把环上距离全都消成 $0$ 即可。
具体的操作就是先对最后的状态忽略环跑出一棵树，然后用 $\text{dfs3}$ 把环上距离都消成 $0$ 。逆向遍历操作，对于操作 $1$ 直接查询距离，操作 $2$ 就把两点距离消为 $0$ 。
需要注意删边可能有重复，反过来说就是可能重复加边，所以用map去重。
剩下的就是标准的边权树剖模板了。
#include<bits/stdc++.h>
#define pr pair <int,int>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge {
int next,to;
bool ava;
} edge[200005];
struct Tree {
int left,right,sum,delta;
} tree[120005];
map <pr,int> mp;
int cnt,head[30005],n,m,a,b,c,q[40005][3],qcnt,ans[40005],acnt;
int dfsord,id[30005],fa[30005],son[30005],deep[30005],top[30005],siz[30005];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].ava=1;
head[u]=cnt;
mp[make_pair(u,v)]=cnt;
}
inline void pushup(int x) { tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; }
inline void pushdown(int x)
{
tree[x*2].sum=tree[x*2+1].sum=0;
tree[x*2].delta=tree[x*2+1].delta=1;
tree[x].delta=0;
}
void build(int x,int l,int r)
{
tree[x].left=l;
tree[x].right=r;
if (r-l==1) tree[x].sum=1;
else
{
int mid=(l+r)>>1;
build(x*2,l,mid);
build(x*2+1,mid,r);
pushup(x);
}
}
void update(int x,int l,int r)
{
if (l<=tree[x].left && r>=tree[x].right)
{
tree[x].sum=0;
tree[x].delta=1;
}
else
{
if (tree[x].delta) pushdown(x);
int mid=(tree[x].left+tree[x].right)>>1;
if (l<mid) update(x*2,l,r);
if (r>mid) update(x*2+1,l,r);
pushup(x);
}
}
int query(int x,int l,int r)
{
if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
else
{
if (tree[x].delta) pushdown(x);
int ans=0,mid=(tree[x].left+tree[x].right)>>1;
if (l<mid) ans+=query(x*2,l,r);
if (r>mid) ans+=query(x*2+1,l,r);
return ans;
}
}
void dfs1(int x,int f,int dep)
{
fa[x]=f;
deep[x]=dep;
siz[x]=1;
int mx=0;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (siz[y] || !edge[i].ava) continue;
dfs1(y,x,dep+1);
siz[x]+=siz[y];
if (siz[y]>mx)
{
mx=siz[y];
son[x]=y;
}
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
id[x]=++dfsord;
if (!son[x]) return;
dfs2(son[x],topf);
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (fa[y]!=x || y==son[x] || !edge[i].ava) continue;
dfs2(y,y);
}
}
inline void upRange(int u,int v)
{
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
update(1,id[top[u]],id[u]+1);
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
if (id[u]!=id[v]) update(1,id[u]+1,id[v]+1);
}
inline int qRange(int u,int v)
{
int ans=0;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ans+=query(1,id[top[u]],id[u]+1);
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
if (id[u]!=id[v]) ans+=query(1,id[u]+1,id[v]+1);
return ans;
}
void dfs3(int x) //找环把距离消为0
{
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (!edge[i].ava) continue;
if (fa[y]==x) dfs3(y);
if (deep[x]>deep[y] && fa[x]!=y) upRange(x,y);
}
}
signed main()
{
n=read(); m=read();
for (int i=1;i<=m;i++)
{
a=read(); b=read();
add(a,b);
add(b,a);
}
for (;;)
{
a=read(); if (a==-1) break; b=read(); c=read();
if (!a) edge[mp[make_pair(b,c)]].ava=edge[mp[make_pair(c,b)]].ava=0; //删除
q[++qcnt][0]=a; q[qcnt][1]=b; q[qcnt][2]=c;
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n+1);
dfs3(1);
for (int i=qcnt;i;i--)
{
int a=q[i][0],b=q[i][1],c=q[i][2];
if (a) ans[++acnt]=qRange(b,c);
else upRange(b,c);
}
for (int i=acnt;i;i--) printf("%d\n",ans[i]);
return 0;
}