这种不断删边的首先肯定想到时光倒流啊=。=
在最后剩下的连通图上跑出一棵搜索树，先将边权都赋为$1$，那么两点间的关键航线就是链上边权和，而每加入一条非树边$u,v$都会使得$u,v$链上的边的边权变为零。写个树剖，先把非树边加进去，然后逆着做一下就行了。
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,Q=;
struct a
{
int n1,n2,t;
int mn(){return min(n1,n2);}
int mx(){return max(n1,n2);}
}edg[M],qry[Q];
bool operator < (a x,a y)
{
return x.mn()==y.mn()?x.mx()<y.mx():x.mn()<y.mn();
}
map<a,bool> mp;
int n,m,typ,tot,num,cnt;
int p[N],noww[*M],goal[*M];
int vis[N],outp[Q],val[*N],laz[*N];
int dfn[N],siz[N],anc[N],dep[N],imp[N],top[N];
void link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
void DFS(int nde,int fth,int dth)
{
int tmp=;
siz[nde]=,vis[nde]=true;
anc[nde]=fth,dep[nde]=dth;
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&!vis[goal[i]])
{
mp[(a){nde,goal[i],}]=true;
DFS(goal[i],nde,dth+);
siz[nde]+=siz[goal[i]];
if(siz[goal[i]]>tmp)
tmp=siz[goal[i]],imp[nde]=goal[i];
}
}
void mark(int nde,int tpp)
{
top[nde]=tpp,dfn[nde]=++num;
if(imp[nde])
{
mark(imp[nde],tpp);
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=imp[nde]&&goal[i]!=anc[nde])
mark(goal[i],goal[i]);
}
}
void create(int nde,int l,int r)
{
if(l==r)
val[nde]=,laz[nde]=-;
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
create(ls,l,mid),create(rs,mid+,r);
val[nde]=val[ls]+val[rs],laz[nde]=-;
}
}
void release(int nde,int l,int r)
{
if(~laz[nde])
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
laz[ls]=laz[nde],laz[rs]=laz[nde];
val[ls]=(mid-l+)*laz[nde];
val[rs]=(r-mid)*laz[nde];
laz[nde]=-;
}
}
void change(int nde,int l,int r,int nl,int nr,int task)
{
if(l>nr||r<nl)
return ;
else if(l>=nl&&r<=nr)
val[nde]=task*(r-l+),laz[nde]=task;
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+; release(nde,l,r);
change(ls,l,mid,nl,nr,task),change(rs,mid+,r,nl,nr,task);
val[nde]=val[ls]+val[rs];
}
}
int query(int nde,int l,int r,int nl,int nr)
{
if(l>nr||r<nl)
return ;
else if(l>=nl&&r<=nr)
return val[nde];
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+; release(nde,l,r);
return query(ls,l,mid,nl,nr)+query(rs,mid+,r,nl,nr);
}
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y); x=anc[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void path_change(int x,int y)
{
int lca=LCA(x,y),mem=query(,,n,dfn[lca],dfn[lca]);
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(,,n,dfn[top[x]],dfn[x],); x=anc[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(,,n,dfn[x],dfn[y],),change(,,n,dfn[lca],dfn[lca],mem);
}
int path_query(int x,int y)
{
int ret=;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret+=query(,,n,dfn[top[x]],dfn[x]); x=anc[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
int lca=LCA(x,y),dec=query(,,n,dfn[lca],dfn[lca]);
return ret+query(,,n,dfn[x],dfn[y])-dec;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&edg[i].n1,&edg[i].n2);
mp[edg[i]]=true;
}
while(scanf("%d",&typ)&&~typ)
{
qry[++tot].t=typ;
scanf("%d%d",&qry[tot].n1,&qry[tot].n2);
if(!typ) mp[qry[tot]]=false;
}
for(int i=;i<=m;i++)
if(mp[edg[i]])
{
link(edg[i].n1,edg[i].n2);
link(edg[i].n2,edg[i].n1);
}
mp.clear(); DFS(,,);
memset(p,,sizeof p),cnt=;
for(int i=;i<=m;i++)
if(mp[edg[i]])
{
link(edg[i].n1,edg[i].n2);
link(edg[i].n2,edg[i].n1);
}
mark(,); create(,,n);
for(int i=;i<=tot;i++)
if(!qry[i].t) mp[qry[i]]=true;
for(int i=;i<=m;i++)
if(!mp[edg[i]]) path_change(edg[i].n1,edg[i].n2);
for(int i=tot;i;i--)
{
if(qry[i].t) outp[++outp[]]=path_query(qry[i].n1,qry[i].n2);
else path_change(qry[i].n1,qry[i].n2);
}
while(outp[]) printf("%d\n",outp[outp[]--]);
return ;
}