题目链接
给出 \(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\) 级祖先。

阅读全文 »