UVA1464 Traffic Real Time Query System/Acwing398. 交通实时查询系统(UVA)

UVA1464 Traffic Real Time Query System/Acwing398. 交通实时查询系统(Acwing)

\(\text{Solution:}\)

首先一眼看上去就是扔一个点双缩点 \(vcc\) 然后再丢倍增啥的直接搞。搞完发现问的是边……

考虑对每条边处理好它所在的点双编号。如果一条边的两个点都在某一个点双里面，就把它标记成这个点双。否则看它到底是连的哪个边双，标记即可。

那么剩下的就是一个缩点后树上的 \(LCA\) 了。关于统计答案，要处理出树上路径的割点数目，打个标记树上差分一类就好了。

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int N=20001;
const int M=400001;
const int SN=16;
int head[N],Head[N],tot,tto,n,m;
struct E {
	int nxt,to,pos;
} e[M>>1],edge[M];
inline void link(int u,int v,int pos=0,int opt=0) {
	if(opt!=0) {
		edge[++tto]=(E) {
			Head[u],v,pos
		};
		Head[u]=tto;
		return;
	}
	e[++tot]=(E) {
		head[u],v,pos
	};
	head[u]=tot;
}
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	int s=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){
		s=s*10-'0'+ch;
		ch=getchar();
	}
	return s;
}
int dfn[N],st[N],top,low[N],dfstime,vis[N];
inline int Min(int x,int y) {return x<y?x:y;}
inline int Max(int x,int y) {return x>y?x:y;}
struct EE{int u,v;}ee[M];
vector<int>dcc[N];
int dccnum,id[M];
void tarjan(int x,int root) {
	dfn[x]=low[x]=++dfstime;
	st[++top]=x;
	if(x==root&&!head[x]){
		dcc[++dccnum].push_back(x);
		return;
	}
	int ch=0;
	for(int i=head[x]; i; i=e[i].nxt) {
		int j=e[i].to;
		if(!dfn[j]) {
			tarjan(j,root);
			low[x]=Min(low[x],low[j]);
			++ch;
			if(low[j]>=dfn[x]) {
				if(x!=root||ch>1)vis[x]=1;
				++dccnum;
				int vex=-1;
				do {
					vex=st[top--];
					dcc[dccnum].push_back(vex);
				} while(vex!=j);
				dcc[dccnum].push_back(x);
			}

		} else low[x]=Min(low[x],dfn[j]);
	}
}
int Node[N],c[N],Q,f[N][SN],dep[N],d[N];
void clear() {
	for(int i=1; i<=(n<<1); ++i)dfn[i]=d[i]=low[i]=dep[i]=head[i]=Head[i]=vis[i]=c[i]=Node[i]=0,dcc[i].clear();
	for(int i=1; i<=(n<<1); ++i)
		for(int j=0; j<SN; ++j)
			f[i][j]=0;
	for(int i=1;i<=m;++i)id[i]=0;
	for(int i=1; i<=top; ++i)st[i]=0;
	top=0;
	tto=1;
	tot=1;
	dccnum=0;
	dfstime=0;
}
void DFS(int x,int fa) {
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	d[x]=d[fa];
	if(x>dccnum)d[x]++;
	for(int i=1; i<SN; ++i)f[x][i]=f[f[x][i-1]][i-1];
	for(int i=Head[x]; i; i=edge[i].nxt) {
		int j=edge[i].to;
		if(j==fa)continue;
		DFS(j,x);
	}
}
int LCA(int x,int y) {
	if(dep[x]<dep[y])swap(x,y);
	for(int i=SN-1; ~i; --i)if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)return x;
	for(int i=SN-1; ~i; --i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int calc(int u,int v){
	int L=LCA(u,v);
	return d[f[u][0]]+d[f[v][0]]-d[L]-d[f[L][0]];
}
inline int getpos(int v){return Max(c[v],Node[v]);}
int main() {
	do {
		clear();
		n=read();m=read();
		if(n==0&&m==0)break;
		for(int i=1; i<=m; ++i) {
			int u=read(),v=read();
			link(u,v,i);
			link(v,u,i);
			ee[i]=(EE){u,v};
		}
		for(int i=1; i<=n; ++i)if(!dfn[i])top=0,tarjan(i,i);
		int numb=dccnum;
		for(int i=1; i<=n; ++i)if(vis[i])Node[i]=++numb;
		for(int i=1; i<=dccnum; ++i) {
			for(auto v:dcc[i]){
				c[v]=i;
			}
			for(auto v:dcc[i]) {
				for(int vv=head[v];vv;vv=e[vv].nxt){
					int j=e[vv].to;
					if(c[j]==i)id[e[vv].pos]=i;
				}
				if(vis[v]){
					link(Node[v],i,0,727);
					link(i,Node[v],0,727);
				}
			}
		}
		for(int i=1;i<=numb;++i)if(!dep[i])DFS(i,i);
		Q=read();
		while(Q--) {
			int u=read(),v=read();
			printf("%d\n",calc(id[u],id[v]));
		}
	} while(!(n==0&&m==0));
	return 0;
}