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

路径的长度。

l

可以通过倍增 LCA 在

O( \log n)

的时间复杂度求出。

最终总时间复杂度为

O(q \log n)

。

UVA1464 Traffic Real Time Query System 题解

文章操作

UVA1464 Traffic Real Time Query System 题解

题目大意

思路