对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。
星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编号1、2、3……。
一些先遣飞船已经出发，在星球之间开辟探险航线。
探险航线是双向的，例如从1号星球到3号星球开辟探险航线，那么从3号星球到1号星球也可以使用这条航线。
例如下图所示：
在5个星球之间，有5条探险航线。
A、B两星球之间，如果某条航线不存在，就无法从A星球抵达B星球，我们则称这条航线为关键航线。
显然上图中，1号与5号星球之间的关键航线有1条：即为4-5航线。
然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时回复这些航线，可见两个星球之间的关键航线会越来越多。
假设在上图中，航线4-2（从4号星球到2号星球）被破坏。此时，1号与5号星球之间的关键航线就有3条：1-3，3-4，4-5。
小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。
Input第一行有两个整数N，M。表示有N个星球（1< N < 30000），初始时已经有M条航线（1 < M < 100000）。随后有M行，每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线；C为0表示在星球A和星球B之间的航线被破坏，当后面再遇到C为1的情况时，表示询问航线被破坏后，关键路径的情况，且航线破坏后不可恢复； C为-1表示输入文件结束，这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。
Output对每个C为1的询问，输出一行一个整数表示关键航线数目。
Hint我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。
Solution首先这题离线逆序处理不必多说了，这类删除点/边题固定套路
刚看到这题的想法是 \(Tarjan\) 缩点然后怎么拓扑乱搞求一下距离
然而这是一个无向图并不存在拓扑序
然而我并不会求距离
我们注意到 \(Hint\) 里面保证了这么一句话在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。
题目保证不存在重边，而且互相连通，又是无向图...想到了什么？缩完点后的图是一棵树啊！
也就是说，我们需要动态的维护树上点之间的距离
树上把点连起来的是什么？边啊！
那么我们需要维护树上两点之间的边权不就行了！
想到了什么？树链剖分！
对，我们可以树剖维护树上的边权，这样就可以轻而易举的求出树上两点之间的距离了。
那...怎么动态缩点呢？
做这题时，我为这事纠结了半天...
然后才发现，既然能维护树上两点间距离，那还缩点干啥呢？
直接将一个环内的点之间的边权赋为0不就行了！
算法流程如下：
读入询问，逆序处理
先随便在原图中求出一棵生成树，我直接用 \(dfs\) 序实现的
然后用那些没被删除的非树边先更新一遍当前的边权
树剖裸题。
因为是边权下放到点权，注意修改的时候不要改它们的 \(lca\) ！
Code#include<map> #include<cstdio> #include<cctype> #define N 30005 #define Q 40005 #define M 100005 #define max(A,B) ((A)>(B)?(A):(B)) #define min(A,B) ((A)<(B)?(A):(B)) #define swap(A,B) ((A)^=(B)^=(A)^=(B)) int n,m,d[N],ans[Q]; std::map<int,int> mp; int cnt,tot,son[N],pos; int val[N],head[N],fa[N]; int dfn[N],top[N],ques[Q][5]; int sze[N],sum[N<<2],lazy[N<<2]; struct Edge{ int to,nxt,ok; }edge[M<<1]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; mp[x*(n+1)+y]=cnt;; } int getint(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; } void first_dfs(int now){ sze[now]=1; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(sze[to] or edge[i].ok) continue; d[to]=d[now]+1; fa[to]=now; first_dfs(to); sze[now]+=sze[to]; if(sze[to]>sze[son[now]]) son[now]=to; } } void second_dfs(int now,int low){ dfn[now]=++tot; top[now]=low; if(son[now]) second_dfs(son[now],low); for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(fa[to]!=now or to==son[now] or edge[i].ok) continue; second_dfs(to,to); } } void pushup(int cur){ sum[cur]=sum[cur<<1]+sum[cur<<1|1]; } void build(int cur,int l,int r){ if(l==r){ sum[cur]=1; return; } int mid=l+r>>1; build(cur<<1,l,mid); build(cur<<1|1,mid+1,r); pushup(cur); } void pushdown(int cur){ if(!lazy[cur]) return; sum[cur<<1]=sum[cur<<1|1]=0; lazy[cur<<1]=lazy[cur<<1|1]=1; lazy[cur]=0; } void modify(int cur,int l,int r,int ql,int qr){ if(ql<=l and r<=qr){ sum[cur]=0; lazy[cur]=1; return; } pushdown(cur); int mid=l+r>>1; if(ql<=mid) modify(cur<<1,l,mid,ql,qr); if(mid<qr) modify(cur<<1|1,mid+1,r,ql,qr); pushup(cur); } void change(int x,int y){ while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); modify(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]<d[y]) swap(x,y); if(d[x]!=d[y]) modify(1,1,n,dfn[y]+1,dfn[x]); } void third_dfs(int now){ for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(edge[i].ok) continue; if(fa[to]==now) third_dfs(to); if(fa[now]!=to and d[to]<d[now]) change(to,now); } } int query(int cur,int l,int r,int ql,int qr){ if(ql<=l and r<=qr) return sum[cur]; pushdown(cur); int mid=l+r>>1,now=0; if(ql<=mid) now+=query(cur<<1,l,mid,ql,qr); if(mid<qr) now+=query(cur<<1|1,mid+1,r,ql,qr); return now; } int ask(int x,int y){ int now=0; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); now+=query(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]<d[y]) swap(x,y); now+=query(1,1,n,dfn[y],dfn[x]); now-=query(1,1,n,dfn[y],dfn[y]); return now; } signed main(){ n=getint(),m=getint(); for(int i=1;i<=m;i++){ int x=getint(),y=getint(); add(x,y); add(y,x); } while(1){ int a=getint(); if(a==-1) break; int b=getint(),c=getint(); ques[++pos][1]=a; ques[pos][2]=b; ques[pos][3]=c; if(a==0) edge[mp[b*(n+1)+c]].ok=edge[mp[c*(n+1)+b]].ok=1; } d[1]=1; first_dfs(1); second_dfs(1,1); build(1,1,n); third_dfs(1); for(int i=pos;i;i--){ if(ques[i][1]) ans[i]=ask(ques[i][2],ques[i][3]); else change(ques[i][2],ques[i][3]); } for(int i=1;i<=pos;i++){ if(ques[i][1]!=1) continue; printf("%d\n",ans[i]); } return 0; }