洛谷P2783 有机化学之神偶尔会做作弊题解

题意：

给你一个 \(n\) 个点，\(m\) 条边的无向图。

把图中所有的环变为一个点，求变化后某两个点之间有多少个点。

输入格式：

第一行两个整数 \(n,m\)。表示有 \(n\) 个点，\(m\) 根键。

接下来 \(m\) 行每行两个整数 \(u,v\) 表示 \(u\) 号碳和 \(v\) 号碳有一根键。

接下来一个整数 \(q\) 表示询问次数。

接下来 \(q\) 行每行两个整数，\(a,b\) 表示询问的两个碳的编号。

输出格式：

共 \(q\) 行，每行一个二进制数，表示答案。

数据范围：

对于 \(100\%\) 的数据，\(1<n\le10 ^ 4\)，\(1<m\le5\times 10 ^ 4\)。

还以为是什么好玩的化学题，搞了半天就是个板子题

思路是缩点以后维护前缀和，查询用 LCA 。

给不知道这个 trick 的同学讲一下吧，因为缩点以后一定是无环的，但不一定是链

所以我们钦定一个根，从叶子递归到根求出前缀和 \(d_i\) 。

那么树上任意两个点 \(u,v\) 的点距离即为 \(d_u + d_v - d_{\mathrm{LCA}(u,v)}-d_{\mathrm{fa}(\mathrm{LCA}(u,v))}\)

时间复杂度 \(\mathcal{O}(n\log n)\)

代码：（题解区搬的）

#include<bits/stdc++.h>
#define N 100008
#define R register
using namespace std;
inline void in(int &x)
{
	int f=1;x=0;char s=getchar();
	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
	while(isdigit(s)){x=x*10+s-'0';s=getchar();}
	x*=f;
}
int n,m,head[N],tot,dfn[N],low[N],stk[N],top,idx,h[N],ttt;
struct code{int u,v;}edge[N<<3],e[N<<3];
int belong[N],col,dis[N],depth[N],f[N][21];
int q;
bool inq[N];
inline void add(int x,int y)
{
	e[++tot].u=h[x];
	e[tot].v=y;
	h[x]=tot;
}
inline void ado(int x,int y)
{
	edge[++ttt].u=head[x];
	edge[ttt].v=y;
	head[x]=ttt;
}
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++idx;
	stk[++top]=x;inq[x]=true;
	for(R int i=h[x];i;i=e[i].u)
	{
		if(e[i].v==fa)continue;
		if(!dfn[e[i].v])
		{
			tarjan(e[i].v,x);
			low[x]=min(low[x],low[e[i].v]);
		}
		else if(inq[e[i].v])
			low[x]=min(low[x],dfn[e[i].v]);
	}
	if(dfn[x]==low[x])
	{
		col++;
		int now=-1;
		while(now!=x)
		{
			now=stk[top--];
			inq[now]=false;
			belong[now]=col;
		}
	}
}
void dfs(int u,int fa)
{
	f[u][0]=fa;
	dis[u]=dis[fa]+1;
	depth[u]=depth[fa]+1;
	for(R int i=1;(1<<i)<=depth[u];i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(R int i=head[u];i;i=edge[i].u)
	{
		if(edge[i].v==fa)continue;
		dfs(edge[i].v,u);	
	}
}
inline int lca(int x,int y)
{
	int res=0;
	if(depth[x]>depth[y])swap(x,y);
	for(R int i=17;i>=0;i--)
		if(depth[x]+(1<<i)<=depth[y])
			y=f[y][i];
	if(x==y)return y;
	for(R int i=17;i>=0;i--)
	{
		if(f[x][i]==f[y][i])continue;
		x=f[x][i],y=f[y][i];		
	}
	return f[x][0];
}
int main()
{
	in(n),in(m);
	for(R int i=1,x,y;i<=m;i++)
	{
		in(x),in(y);
		add(x,y),add(y,x);
	}
	for(R int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i,0);
	for(R int i=1;i<=n;i++)
		for(R int j=h[i];j;j=e[j].u)
			if(belong[i]!=belong[e[j].v])
				ado(belong[i],belong[e[j].v]);

	dfs(belong[1],0);
	in(q);
	for(R int x,y,la;q;q--)
	{
		in(x),in(y);
		x = belong[x], y = belong[y];
		la=lca(x,y);
		int ans=dis[x]+dis[y]-2*dis[la]+1;
		int size[15]={0},cnt=0;
		while(ans)
		{
			size[++cnt]=ans%2;
			ans/=2;
		}
		for(R int i=cnt;i>=1;i--)
			printf("%d",size[i]);
		putchar('\n');
	}
}