P2934 [USACO09JAN] Safe Travel G——无向图最短路树及其性质

题面很简单，就是求出不走原本最短路最后一条边的情况下1号点到每个点的距离

一个错误的想法是，一边dijkstra搞掉原本最短路顺便记录最后一条边，然后查询每个点的时候就用这个点的邻接边去重新更新它

但是这样是错的，因为有些后边的点的最短路是依赖于这条边的，所以这些点的最短路也要相应发生改变

既然发现了这种依赖关系，就可以考虑用树来表达它

也就是说，从源点到所有点的所有最短路径并起来是一棵树（最短路径唯一的情况下）

这很显然，联通并且依赖的最后一条边只有一条，n-1条边的无向连通图

接下来考虑最短路树和我们要求的路径有什么关系

发现当断开一条边时，会发生改变的就只有这条边以下的点，而想要再到达这个点就必须走一条跨越两个子树的边

那么首先要证明的是，所走的路径中不在原树上的的只有这一条

如果加入了其它的边，并且优于原本只走一条的路径的话，那么最短路树上本来就应该有这一条边，证毕

于是，我们就只需要找所有跨越这两个子树的边，把它们的答案取一个最小即可

这条边确定后，这条路径的长度就为

$u,v$ 为边的两端， $w$ 为边权， $i$ 为被切掉的边的下方节点
$dis$ 为原树上到 $1$ 的距离

发现两部分相互独立，显然可以试着把问题转化成每条边会对怎样的点造成贡献

发现一条非树边可以造成的贡献是两个端点到LCA的路径扣掉LCA，原因与横跨两棵子树有关

到这里就可以用树链剖分做 $\log^2$ 做法了

但是还是可以更精细一点，因为是最小值覆盖，只有最后最小值盖的那一下有用

可以直接从小到大排序，在树上用类似 白雪皑皑 的做法进行覆盖，并查集维护染色区间