[AHOI2005] 航线规划

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\n",ans[i]);

	}

	return 0;

}

巴特西