记录编号	577220	评测结果	AAAAAAAAAA
题目名称	[HDOJ 3686]交通实时查询系统	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2022-10-26 21:40:49	内存使用	13.47 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 40001,M = 400001;

struct Edge {
	int from,to,nxt;
}edge[M],edge2[M];

int tot,cnt,head[N],head2[N],num;

void add(int u,int v) {
	edge[++tot].from = u;
	edge[tot].to = v;
	edge[tot].nxt = head[u];
	head[u] = tot;
}

void add2(int u,int v) {
	edge2[++cnt].from = u;
	edge2[cnt].to = v;
	edge2[cnt].nxt = head2[u];
	head2[u] = cnt;
}

int dfn[N],low[N],dfnc,n,m,zhan[N],top;

void tarjan(int now,int fa) {//找点双联通分量,缩点,构造圆方树
	dfn[now] = low[now] = ++dfnc;//初始化
	zhan[++top] = now;//当前结点入栈
	for(int i = head[now]; i != -1; i = edge[i].nxt) {
		int succ = edge[i].to;//now-->succ后继
		if(!dfn[succ]) {//未访问
			tarjan(succ,now);
			low[now] = min(low[now],low[succ]);
			if(dfn[now]<= low[succ]) {//now为割点
				num++;//新点，方点
				add2(num,now),add2(now,num);//now和方点连边
				while(1) {//弹出栈中的所有点,这些点属于同一点双
					int x = zhan[top--];
					add2(x,num),add2(num,x);//分别和方点连边
					if(x == succ) break;
				}
			}
		}
		else if(succ!= fa) {//非搜索树边
			low[now] = min(low[now],dfn[succ]);
		}
	}
}

int f[N][22],dep[N];
bool vis[N];

void dfs(int now,int fa){
	vis[now] = 1;//访问标记
	dep[now] = dep[fa]+1;//深度
	f[now][0] = fa;//2^0辈祖先
	for(int i = 1; (1<<i) <= dep[now]; i++)//为倍增求LCA准备
	{//求now的2^i辈祖先：now的2^(i-1)辈祖先的2^(i-1)辈祖先
		f[now][i] = f[f[now][i-1]][i-1];//爸爸的爸爸叫爷爷
	}
	for(int i = head2[now]; i!= -1; i = edge2[i].nxt) {
		int succ = edge2[i].to;
		if(succ!= fa && !vis[succ]) {
			dfs(succ,now);
		}
	}
}

int LCA(int x,int y) {//树上倍增求LCA
	if(dep[x]>dep[y]) swap(x,y);
	int len = dep[y]-dep[x],k = 0;
	while(len) {
		if(len&1) y = f[y][k];
		k++,len >>= 1;
	}
	if(x == y) return x;
	for(int i = 20;i >= 0;i--) {
		if(f[x][i] == f[y][i]) continue;
		x = f[x][i],y = f[y][i];//同时上跳2^i步
	}
	return f[x][0];
}

int solve(int x,int y) {
	return (dep[x]+dep[y]-2*dep[LCA(x,y)])/2-1; 
}//圆方树：圆点和方点交替出现，故需/2排除方点

int main() {
	freopen("traffic_query.in", "r", stdin);
	freopen("traffic_query.out", "w", stdout);
	while(scanf("%d%d",&n,&m)!= EOF && (n|m))
	{//多组数据
		memset(head,-1,sizeof(head));
		memset(head2,-1,sizeof(head2));
		memset(edge,0,sizeof(edge));
		memset(edge2,0,sizeof(edge2));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(f,0,sizeof(f));
		memset(dep,0,sizeof(dep));
		memset(zhan,0,sizeof(zhan));
		memset(vis,0,sizeof(vis));
		tot = 0,cnt = 0,dfnc = 0,top = 0,num = n;
		for(int i = 1;i<= m;i++) {
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v); add(v,u);
		}
		for(int i = 1;i<= n;i++)
		{//对点双缩点并构造圆方树
			if(!dfn[i]) tarjan(i,-1);
		}
		for(int i = 1;i<= num;i++)
		{//dfs求结点i的深度和2^x辈祖先
			if(!vis[i]) dfs(i,0);
		}
		int q;
		scanf("%d",&q);
		while(q--) {
			int s,t;
			scanf("%d%d",&s,&t);//起始边
			//边到边 转化为 点到点
			int ans1 = solve(edge[s*2].from,edge[t*2].from);
			int ans2 = solve(edge[s*2].from,edge[t*2].to);
			int ans3 = solve(edge[s*2].to,edge[t*2].from);
			int ans4 = solve(edge[s*2].to,edge[t*2].to);
			int ans = max(max(ans1,ans2),max(ans3,ans4));
			printf("%d\n",ans);
		}
	}
	return 0;
}