【bzoj4699】树上的最短路

Source

bzoj4699

Hint

请先思考后再展开

请时刻记住这永远是一棵树,坍塌的两端都是树上路径
坍塌因为有多个起点,只需要从最短距离的起点出发
边权都是正数,可以dij

Solution

请先思考后再展开

把树边也记为坍塌,建反向边求单源最短路
先考虑直接转化为新图,然后发现诸如线段树优化建图什么的都不太行
那就考虑在dij的过程中利用边

首先,如何取出经过点x的所有坍塌?这里的取出就是用完之后删除,正如hint中说的,这条坍塌已经没用了
情况1:一个在子树内,一个在子树外,则可以配合dfs序在线段树上查询极值取出路径
情况2:来自x的不同孩子,这种把路径挂在lca处即可
注意每条路径可能被取出常数次,判不判重都行

设点y在路径上,如果y在dij的前面已经出去拓展,而边权又都是正的,则y不再需要出去拓展
那么因为这个路径的终点都是相同的代价,则可以把路径也一起塞到堆里面(相当于一个新点)
然后因为会更新一条树上路径,先考虑让每个点只被更新一次,好像不太可行
但如果我们能让每个点只拓展别人一次,那也是可以的保证复杂度的
那么我们可以把路径拆为(dis,x,lca)和(dis,y,lca)这样向上的路径
然后每个点用个并查集维护向上第一个目前依然没有出去拓展的点

复杂度为 $O(mlogn)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/271b.html
转载请注明出处,谢谢!