保证了无论怎么破坏航线，图都会是一个连通图
也就是说，起码肯定有一棵生成树
考虑在生成树上U，V之间加边，会对树上各个点的割边情况产生什么影响
对于任意点对(u,v)，如果它们之间的最短路径不经过从U到V的树上路径，那是没有影响的
否则：关键路径的数目会减少
减少了多少？U，V之间树上路径经过的所有边
启发了我们可以把维护割边转化成区间加，树上的区间加当然是用树链剖分处理了
查询询问时，答案就是u到v的路径上没有被覆盖的边
（为什么这样是对的？如果被覆盖了，显然可以从其他边走，就不是割边了）
但是删边不好处理，考虑到询问可以离线，把所有询问离线下来逆向处理，就只有加边而无删边操作了
有一些要注意的细节：
因为维护的其实是边权，所以要把点权下放到边权，修改的时候记得特判一下lca（细节见代码）
其次是，在不考虑会被删掉的边之外，剩下的图任然是一个连通图，不一定是树
那些既没在树上的，又没被删掉的边，要在处理询问前先加回去（不然有笨蛋会get 0 tips）
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; const int maxn=2*int(1e5)+7; ll cnt=0,ecnt=1; ll n,m,R,old[maxn],id[maxn],wt[maxn],top[maxn],son[maxn],head[maxn],fa[maxn],siz[maxn],dep[maxn]; ll mod,a[maxn<<2],lazy[maxn<<2],w[maxn]; int ed[maxn],vis[maxn],ontree[maxn<<1]; struct lys{ int from,to,nex; }e[maxn*2]; void addedge(int from,int to){ ecnt++;e[ecnt].from=from;e[ecnt].to=to;e[ecnt].nex=head[from];head[from]=ecnt; } void dfs1(int u,int f){ vis[u]=1; siz[u]=1; fa[u]=f; dep[u]=dep[f]+1; int maxson=-1; for(int i=head[u];i;i=e[i].nex){ int to=e[i].to; if(to==f||vis[to]) continue; ed[to]=i; ontree[i]=ontree[i^1]=1; dfs1(to,u); siz[u]+=siz[to]; if(siz[to]>maxson) son[u]=to,maxson=siz[to]; } } void dfs2(int u,int topf){ vis[u]=1; cnt++;// dfs order id[u]=cnt; old[cnt]=u; wt[cnt]=w[u]; top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=head[u];i;i=e[i].nex){ int to=e[i].to; if(to==son[u]||to==fa[u]||vis[to]) continue; dfs2(to,to); } } void pushup(int rt){ a[rt]=a[rt<<1]+a[rt<<1|1]; } void build(int rt,int l,int r){ // lazy[rt]=0; if(l==r){ a[rt]= (ed[old[l]]!=-1); return; } int mid=(l+r)>>1; build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); pushup(rt); } void pushdown(int rt,int l,int r){ if(lazy[rt]){ lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; a[rt<<1]=a[rt<<1|1]=0; lazy[rt]=0; } } void add(int rt,int l,int r,int ql,int qr,ll k){ if(ql<=l&&r<=qr){ lazy[rt]+=k; a[rt]=0; return; } int mid=(l+r)>>1; pushdown(rt,l,r); if(ql<=mid) add(rt<<1,l,mid,ql,qr,k); if(mid<qr) add(rt<<1|1,mid+1,r,ql,qr,k); pushup(rt); } void addpath(int x,int y,ll k=1){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); add(1,1,n,id[top[x]],id[x],k); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); //在同一条链上 // if dep[x]==dep[y] do nothing,else if(dep[x]^dep[y]) add(1,1,n,id[x]+1,id[y],k); } ll query(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ return a[rt]; } pushdown(rt,l,r); int mid=(l+r)>>1;ll ans=0; if(mid>=ql) ans+=query(rt<<1,l,mid,ql,qr); if(mid<qr) ans+=query(rt<<1|1,mid+1,r,ql,qr); pushup(rt); return ans; } ll qpath(int x,int y){ ll ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); // dep[x]<=dep[y] ans+=query(1,1,n,id[x],id[y]); // 减去lca ans-=query(1,1,n,id[x],id[x]); return ans; } map<ll,int>use; int ID(int x,int y){ return x*10000+y; } int x[maxn],y[maxn],ans[maxn]; struct query{ int c,x,y; }Q[maxn]; int main(){ //freopen("lys.in","r",stdin); memset(ed,-1,sizeof(ed)); fastio; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>x[i]>>y[i]; } int qcnt=0; while(1){ int c,xx,yy;cin>>c; if(c==-1) break; qcnt++; cin>>xx>>yy; Q[qcnt].c=c;Q[qcnt].x=xx,Q[qcnt].y=yy; if(c==0) use[ID(xx,yy)]=use[ID(yy,xx)]=1; } for(int i=1;i<=m;i++){ if(use[ID(x[i],y[i])]||use[ID(y[i],x[i])]) continue; //连通图，但不一定是树边 addedge(x[i],y[i]); addedge(y[i],x[i]); } // 建立生成树 dfs1(1,0); memset(vis,0,sizeof(vis)); dfs2(1,1); build(1,1,n); for(int i=2;i<=ecnt;i++){ int X=e[i].from,Y=e[i].to; if(use[ID(X,Y)]||use[ID(Y,X)]) continue;//Be deleted if(ontree[i]||ontree[i^1]) continue; addpath(X,Y); } for(int i=qcnt;i>=1;i--){ if(Q[i].c==0){ addpath(Q[i].x,Q[i].y); } else { ans[i]=qpath(Q[i].x,Q[i].y); } } for(int i=1;i<=qcnt;i++){ if(Q[i].c==1) cout<<ans[i]<<endl; } }