今天写题的时候做到一个非常牛的东西。
给你一个图，\(q\) 次问你如果删掉一条边，\(1\) 到 \(n\) 的最短路会变成多少。
首先搞出来 \(1\) 出发的最短路树，然后如果这条边根本不在这棵树上，显然没有任何影响。
如果在的话，我们必然要绕路了。
给出一个性质：我们选择绕的路至多经过一条原来的非树边。
简单思考一下这是为什么。首先我们假设经过了至少两条非树边。
我们任意选取其中的两条。如果这两条有一条根本就没有跨过删除的边，显然这条边是不优的。否则，因为这两条都是非树边，我们在经过一条边之后，一定存在另一个更加不劣的方式回到主干道上。
所以我们只需要对于每一条边算一下它贡献的树边区间，用一个线段树维护即可。这个贡献的区间的两个端点其实就是在 \(1,n\) 最短路树上分别与这条边两个端点的 lca。注意这两颗最短路树上的 \(1\) 到 \(n\) 的最短路必须相同。
有例题 CF1163F，但是目前没时间写了，先鸽一会。