题解：P15455 [JOI 2026 SemiFinal] 新的桥梁 / New Bridge

水星湖 · 2026-03-27 23:41:08 · 题解

这个是好题啊。

首先题面给的这个算法就是 prim，并且由于保证了边权两两不同，所以不管哪个点开始跑得到的都是唯一的 MST。因此只需要保留这个 MST。

然后你要能想到 kruskal，考虑一条边 (x,y) 合并两个连通块 A,B 的时候（x\in A,y\in B），|A| 对 B 中每个点贡献多少次，显然是所有在 MST 上到达 B 中的点需要经过 A 的点的个数，也就是 MST 删去 (x,y) 之后在 x 这一侧的点的个数 k。要把 B 中所有点答案加上 k\cdot|A|。反之也要考虑 |B| 对 A 中每个点的贡献。kruskal 重构树即可。正确性应该不难理解。