Mst | BZOJ 2238
题目链接
给出 \(n\) 个点，\(m\) 条边的无向带权图，\(q\) 次询问，询问在图中删掉一条边后的 \(\text{MST}\) 的边权和。询问独立。
\(n \leq 5 \times 10^4, m \leq 10^5\)。
记原图的 \(\text{MST} = (E_{\text{MST}}, V_{\text{MST}})\)。
对于 \(e(u, v, w) \not \in E_{\text{MST}}\)（下文称为非树边），将它删去后显然不会对答案造成任何影响。
对于 \(e(u, v, w) \in E_{\text{MST}}\)（下文称为树边），将它删去后，为了使得点 \(u, v\) 仍然连通，我们必须要找一条非树边代替之，且这条非树边 \(e'(u', v', w')\) 所连接的顶点 \((u', v')\)，在 \(\text{MST}\) 上的路径必定覆盖了 \((u, v)\)。
自然的，我们想到枚举每一条非树边，并将其所连接的两个节点在 \(\text{MST}\) 上的路径中的所有树边更新。
更具体的，记 \(f_e\)（其中 \(e\) 为一条树边）为能代替 \(e\) 的非树边的最小权值。一开始 \(f_e = +\infty\)。对于枚举到的非树边 \(e'(u', v', w')\)，更新所有 \(e \in E'\)（其中 \(E'\) 代表 \((u', v')\) 在 \(\text{MST}\) 上的路径）的 \(f_e \leftarrow \min(f_e, w')\)。
问题转化为如何维护这个过程。
一个经典的解法是利用树链剖分与线段树，网络上大多数的题解也是如此。不过这样做的复杂度是 \(O(n \log^2 n)\) 的，且代码长度较长。
我们采用一种码量更少，复杂度更为优秀的 \(O(n \log n)\) 算法，树上倍增来解决。
记录倍增数组 \(\text{fa}(u, k)\) 表示 \(u\) 的 \(2^k\) 级祖先。