UVA1464 Traffic Real Time Query System 题解

Accpter · 2025-04-11 18:43:16 · 题解

UVA1464 Traffic Real Time Query System 题解

题目大意

题目传送门

给出一张 n 个点，m 条边的无向连通图，问从第 s 条边到第 t 号边必须经过多少点。题目有多组数据。

思路

转换问题

这道题类似于 P4320，不过那一题求的是点之间的必经点数，这一题求的是边之间的必经点数。

先建出圆方树，再想如何把边转换成点来做。

根据点双联通分量（下面简称点双）的性质，每条边在且仅在唯一一个点双之中。

所以可以把这条边转换成这条边所在的点双在圆方树中的点，接下来这再求两条边转换成的点之间必须要经过的点。

求边属于的点双

这时候就有一个问题，如何求出一条边所在的点双，先设连接这条边的两个节点编号为 u,v。

根据圆方树的性质，u 和 v 在圆方树上的距离一定为 2，且 u 和 v 路径中间的点一定为这条边所在的点双。

由于距离只有 2，所以 u 和 v 在树上的位置关系只有三种。

下面每种情况都用一张图片举例，为了方便表示，设 fa_a 为 a 的在树上的父亲，最后要求的点双为 x。

第一种情况：u 是 v 父亲的父亲

这种情况需要判断 u=fa_{fa_v}，最后要求的点双 x 为 fa_v。

第二种情况：v 是 u 父亲的父亲

这种情况需要判断 v=fa_{fa_u}，最后要求的点双 x 为 fa_u。

第三种情况：x 是 u 和 v 共同的父亲。

这种情况需要判断 fa_u=fa_v，最后要求的点双 x 即 fa_u。

求最终的答案

通过上面的三种情况，能求的 u 到 v 这条边的点双 x，设另一条边的点双为 y，最终的答案为 x 到 y 的必经点的个数。

根据 P4320 的结论，x 到 y 的必经点的个数即为 x 到 y 路径上割点的个数。

由于 x 和 y 都是点双，手摸几组情况可知 x 到 y 路径上割点的个数为 \frac{l}{2}，其中 l 表示 x 到 y 路径的长度。