「BZOJ 4699」树上的最短路（最短路 + 树链剖分 + 线段树）

题目大意

「BZOJ 4699」树上的最短路

给定一棵 $n$ 个结点的树，第 $i$ 条边的长度为 $l_i$。还要额外地联结 $m$ 次边，第 $j$ 次对于任意 $u$ 在树上路径 $(a_j, b_j)$ 上，$v$ 在树上路径 $(c_j, d_j)$ 上，都从 $u$ 向 $v$ 连一条长度为 $e_j$ 的边。问每个点走到 $k$ 点的最短路。

数据范围：$n \le 2.5 \times 10^5, m \le 10^5$。

思路分析

I like this problem :)

显然树上的边不是复杂度瓶颈。下面我们讨论额外加的边。

暴力建边会有 $O(m \times n^2)$ 条，不可取。由于每次连的边长度相同，我们可以让所有起点向一个点连长度为 $0$ 的边，然后从这个点向另一个点连长度为 $e$ 的边，最后从那个点向所有终点连长度为 $0$ 的边。这样我们就将边数减少到了 $O(m \times n)$。

发现边的端点肯定在树上形成连续的一段，容易让我们想到线段树优化建图。不过这题将序列问题放到了树上，我们考虑树链剖分。因为两点之间在树上只会经过 $O(\log n)$ 条重链，我们考虑对于每一条重链建一棵线段树，然后找出对应的一些区间并连边。这样建出的图的边数是 $O(n \log^2 n)$（将 $n, m$ 算作同阶），再套上 Dijkstra 求最短路后的复杂度是 $O(n \log^3 n)$，不足以通过本题。

考虑树链剖分找 LCA 的过程。每次我们将所在链顶端深度较大的点移到链顶端的父亲结点，直到两个结点到达同一条链上。发现每次将某个结点上移的时候，它经过的总是一条重链的前缀。只有在最后一次，两个结点移动到同一条重链上的时候，它们对应的路径才有可能不是某条重链的前缀。于是，对于那 $O(\log n)$ 个前缀，我们使用前缀优化建边，而对于那一个区间，我们使用线段树优化建边。这样建出的图的边数是 $O(n \log n)$，再套上 Dijkstra 求最短路后的复杂度是 $O(n \log^2 n)$，可以通过本题。

值得注意的是，前缀优化建边的方法不是十分显然。我们用 “向外连一个前缀的边” 来举例。对于每一个点，我们拆出一个虚点，原点向虚点连长度为 $0$ 的边，然后每个虚点向下一个虚点连长度为 $0$ 的边。这样在前缀对应的最后一个点向外连边就等价于在原图上对于前缀上的所有点连出一条边了。

代码实现

#include <cstdio>