自动搬运

查看原文

来自洛谷，原作者为

	b6e0_ ‪

搬运于2025-08-24 22:25:36，当前版本为作者最后更新于2023-09-27 10:12:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathcal O(n)\sim\mathcal O(1)$ 另解。

考虑将每个三角形建（图论中的）一个点，两个三角形有公共边则它们的点之间连一条边，这样形成了一棵树，且每个点的度数最大为 $3$。

考虑对这棵树做拓扑排序的过程，则在几何图形上，相当于每次删掉一个度数为 $2$ 的顶点，最后剩下一个三角形。不妨让一个三角形，以及它在树上对应的点，代表拓扑排序过程中和它一起被删除的几何图形上的那个顶点。这样，除了最后剩下的 $3$ 个顶点，每个顶点都与对应树上的一个点。

边界情况：最后剩下的三个点在查询时比较难处理，不妨给原图添加上 $(1,2,n+1),(1,n+1,n+2),(n+1,n+2,n+3)$ 三个三角形得到一个 $n+3$ 个顶点的多边形，这样剩下的三个点就是 $n+1,n+2,n+3$，不影响查询。这样，初始的 $n$ 个顶点形成了一棵树，且若树以 $1$ 为根，每个点都最多有两个儿子。

这样，我们对于 $n$ 个顶点建出了一棵树。考虑树上的哪些点在原几何图形中是有边相连的。

首先，树边一定在原图中存在。然后，原图中存在的其他边，对应到树上一定是返祖边，且树上除了点 $1,2$，每个点都有恰好一条返祖边。但仅仅靠这些显然不足以快速求出最短路，考虑挖掘性质。

观察到，若有 $x\rightarrow y$ 的一条返祖边，设 $x$ 到 $y$ 的路径上的点是 $x,a_1,a_2,\cdots,a_{m-1},a_m,y$，其中 $fa(a_i)=a_{i+1},fa(x)=a_1,fa(a_m)=y$，则 $a_1,a_2,\cdots,a_{m-1}$ 的返祖边都连向 $y$。

以上三点，考虑拓扑排序的过程都容易证明，画画图，模拟几个例子就行了。

下面考虑怎么求 $x$ 到 $y$ 的最短路。根据性质，$x$ 往它的子树走是一定不优的（除了 $x$ 是 $y$ 的祖先的情况，此时我们不妨交换 $x,y$），所以路径一定是不断走返祖边，到达 LCA 附近，然后分讨一些情况，再不断向下走返祖边到达 $y$。

具体来说，有以下几种情况：

• 若通过返祖边能直接到达 LCA，则路径形如 $x\rightarrow\text{LCA}\rightarrow y$；
• 若通过返祖边能到达 LCA 的某个儿子 $s$，则路径形如 $x\rightarrow s\rightarrow\text{LCA}\rightarrow y$；
• 若通过返祖边能到达 LCA 的父亲，则路径形如 $x\rightarrow fa(\text{LCA})\rightarrow y$；
• 若通过返祖边能到达 LCA 出发的返祖边的终点 $t$，则路径形如 $x\rightarrow t\rightarrow y$；

$\text{LCA},fa(\text{LCA}),t$ 到 $y$ 的部分同理，对几种情况取 $\min$ 即可。

为了判断 $x$ 能否通过返祖边走到某个点，以及求出要走多少次，我们对于返祖边再建出一棵树，上面只需要判断一个点是否在一棵子树内，以及求出每个点的深度。

瓶颈在求 LCA，可以用四毛子做到 $\mathcal O(n)\sim\mathcal O(1)$。

$\mathcal O(n\log n)$ 实现：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=52000;
int n,Q,d[MN],nx[MN],ny[MN],pos[MN],q[MN],fr=1,ba,lc[MN],rc[MN],fa[16][MN],dep[MN],dfn[MN],ed[MN],cnt,dis[MN];
vector<int>g[MN];
inline void adde(int x,int y)
{
	g[x].push_back(y);
	g[y].push_back(x);
	d[x]++,d[y]++;
}
void dfs(int x)
{
	for(int j=1;j<16;j++)
		fa[j][x]=fa[j-1][fa[j-1][x]];
	dep[lc[x]]=dep[rc[x]]=dep[x]+1;
	if(lc[x])
		dfs(lc[x]);
	if(rc[x])
		dfs(rc[x]);
}
inline int LCA(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	int d=dep[x]-dep[y];
	for(int i=0;i<16;i++)
		if((d>>i)&1)
			x=fa[i][x];
	if(x==y)
		return x;
	for(int i=15;~i;i--)
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x],y=fa[i][y];
	return ny[x];
}
void dfs2(int x)
{
	dfn[x]=++cnt;
	for(int y:g[x])
	{
		dis[y]=dis[x]+1;
		dfs2(y);
	}
	ed[x]=cnt;
}
inline bool in(int x,int y)
{
	return dfn[x]<=dfn[y]&&dfn[y]<=ed[x];
}
inline int ask(int x,int y)
{
	if(in(x,y))
		return dis[y]-dis[x];
	if(in(lc[x],y))
		return dis[y]-dis[lc[x]]+1;
	if(in(rc[x],y))
		return dis[y]-dis[rc[x]]+1;
	if(in(ny[x],y))
		return dis[y]-dis[ny[x]]+1;
	return dis[y]-dis[nx[x]]+1;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		adde(i,i%n+1);
	adde(1,n+1),adde(2,n+1);
	adde(1,n+2),adde(n+1,n+2);
	adde(n+2,n+3),adde(n+2,n+3);
	for(int i=0;i<n-3;i++)
	{
		int x=read(),y=read();
		adde(x,y);
	}
	for(int i=1;i<=n;i++)
		if(d[i]==2)
			q[++ba]=i;
	for(int i=1;i<=n;i++)
	{
		int x=q[fr++];
		pos[x]=i;
		for(int y:g[x])
		{
			if(pos[y])
				continue;
			if(nx[x])
				ny[x]=y;
			else
				nx[x]=y;
			if((--d[y])==2)
				q[++ba]=y;
		}
	}
	for(int i=1;i<=n+3;i++)
		g[i].clear();
	pos[n+1]=pos[n+2]=pos[n+3]=MN;
	ny[1]=0;
	for(int i=2;i<=n;i++)
	{
		if(pos[nx[i]]<pos[ny[i]])
			swap(nx[i],ny[i]);
		if(lc[ny[i]])
			rc[ny[i]]=i;
		else
			lc[ny[i]]=i;
		fa[0][i]=ny[i];
	}
	nx[2]=2,nx[1]=1;
	for(int i=3;i<=n;i++)
		g[nx[i]].push_back(i);
	dfs(1);
	dfs2(1),dfs2(2);
	Q=read();
	while(Q--)
	{
		int x=read(),y=read(),l=LCA(x,y),res=MN;
		if(in(l,x))
			res=dis[x]-dis[l]+ask(l,y);
		if(in(ny[l],x))
			res=min(res,dis[x]-dis[ny[l]]+ask(ny[l],y));
		if(in(lc[l],x))
			res=min(res,dis[x]-dis[lc[l]]+1+ask(l,y));
		if(in(rc[l],x))
			res=min(res,dis[x]-dis[rc[l]]+1+ask(l,y));
		if(in(nx[l],x))
			res=min(res,dis[x]-dis[nx[l]]+ask(nx[l],y));
		write(res);
	}
	return 0;
}