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)\)。