over 2 years ago

题目大意

给一个个点条边的连通无向图,满足每条边最多属于一个环,有组询问,每次询问两点之间的最短路径。

分析

题目就是求仙人掌上两点之间的最短路。
思考树上的情况,我们只要求出根到每个点的最短距离,然后求出即可。
对于仙人掌,我们依旧可以求出每个点到根的最短路,然后把环上的每个点向环上深度最浅的点连一条边权为环上最短距离的边,这样我们建出了一棵新的树,我们记点的父边的权值为
考虑仙人掌上两点之间路径构成的特点,发现我们只要特殊考虑以下一种情况:


这种情况我们怎么处理呢?其实我们只要记录分别表示往左边/右边走到环上最浅点的距离,然后把刚好倍增到下面,此时,假设此时环上的左边,设环长为,那么我们要求的就是
$$dis[u]+dis[v]-2dis[LCA]-fw[u']-fw[v']+\min\begin{Bmatrix} d[u'][0]+d[v'][1], l-(d[u'][0]+d[v'][1]) \end{Bmatrix}$$
因此这样我们就可以在的时间内解决了,终于又填了一个坑。
bzoj2125.cpp

← 树上莫队 CF235E →
 
comments powered by Disqus