【题解】LuoGu2783：有机化学之神偶尔会做作弊

原题传送门
没有思维难度的题目
先把环缩成一个点
然后重建图
新图中求两点间距离当然是$d[u]+d[v]-2d[lca]$
本题求的是点个数所以还要加一
最后把答案用二进制输出
Code：

#include <bits/stdc++.h>
#define maxn 50010
using namespace std;
struct Line{
	int x, y;
}line[maxn << 1];
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], dfn[maxn], low[maxn], Index, vis[maxn], top, sta[maxn];
int d[maxn], fa[maxn][25], cnt, a[maxn], n, m, color[maxn], tot;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
} 

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void tarjan(int u, int pre){
	dfn[u] = low[u] = ++Index;
	vis[u] = 1, sta[++top] = u;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			if (!dfn[v]) tarjan(v, u), low[u] = min(low[u], low[v]); else
			if (vis[v]) low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]){
		++tot;
		while (sta[top + 1] != u) vis[sta[top]] = 0, color[sta[top--]] = tot;
	}
}

void dfs(int u, int pre){
	d[u] = d[pre] + 1, fa[u][0] = pre;
	for (int i = 0; fa[u][i]; ++i) fa[u][i + 1] = fa[fa[u][i]][i];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u);
	}
}

int lca(int u, int v){
	if (d[u] > d[v]) swap(u, v);
	for (int i = 20; i >= 0; --i) if (d[u] <= d[v] - (1 << i)) v = fa[v][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

void print(int x){
	int cnt = 0;
	while (x) a[++cnt] = x & 1, x /= 2;
	for (int i = cnt; i; --i) printf("%d", a[i]);
	puts("");
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read();
		line[i].x = x, line[i].y = y;
		addedge(x, y); addedge(y, x);
	}
	for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);
	num = 0;
	memset(head, 0, sizeof(head));
	for (int i = 1; i <= m; ++i){
		int x = color[line[i].x], y = color[line[i].y];
		if (x != y) addedge(x, y), addedge(y, x);
	}
	dfs(1, 0);
	int q = read();
	while (q--){
		int x = color[read()], y = color[read()];
		print(d[x] + d[y] - 2 * d[lca(x, y)] + 1);
	}
	return 0;
}