Description
对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
",ans[i]);
}
return 0;
}