P6976 题解

b6e0_ · 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；