UPD on 8/8：添加了代码。
题目：给定一张 nnn 个点 mmm 条边的无向连通图，每条边有一个边权，定义 dis(u,v)\text{dis}(u,v)dis(u,v) 为 u,vu,vu,v 的最短路。
给出 kkk 个关键点，对 kkk 个点建一个新图，其中对于每对 u,vu,vu,v 连一条权值为 dis(u,v)\text{dis}(u,v)dis(u,v) 的边。求新图 MST。
1≤k≤n,m≤5×1051\le k\le n,m\le 5\times 10^51≤k≤n,m≤5×105。
我怎么现在才知道这个 trick。模拟赛丢大分。
显然不能直接求出 k(k−1)2\frac{k(k-1)}{2}2k(k−1) 个边，考虑优化。
将 kkk 个点一起加入，跑 Dijkstra。对于每个源点分别一种颜色，给它经过的点染色。
比如说这张图，黑点为关键点：
跑最短路后的图：
感性理解一下，这个染色相当于一个类似圆的领域。
注意到一个可能的 MST 边在原路径上不可能经过超过两个颜色。
证明：
假设存在一条边先后经过了 x,y,zx,y,zx,y,z 颜色的点，且生成树中 x,zx,zx,z 连有一条边。
显然此时 dis(x,y),dis(y,z)≤dis(x,z)\text{dis}(x,y),\text{dis}(y,z)\le \text{dis}(x,z)dis(x,y),dis(y,z)≤dis(x,z)。
我们断开 x→zx\to zx→z，然后以 yyy 为一端连向 xxx 或 zzz，显然会形成一棵新生成树，而边权和更小。
所以，我们枚举每条边，判断它两端点的颜色是否不同，如果不同，将它们俩颜色所在关键点连一条边即可。
当然，假设边的两端是 u,vu,vu,v，颜色是 x,yx,yx,y，长度是 lll，加入跑 MST 的边权就是 dis(x,u)+l+dis(y,v)\text{dis}(x,u)+l+\text{dis}(y,v)dis(x,u)+l+dis(y,v)，这个在跑 Dijkstra 的时候已经算好了。
这样，我们就把边数降到了 O(m)O(m)O(m)。
跑一次 Dijkstra 是 O(mlogm)O(m\log m)O(mlogm)，连边跑 Kruskal 求 MST 也是 O(mlogm)O(m\log m)O(mlogm)，所以总复杂度为 O(mlogm)O(m\log m)O(mlogm)。
模拟赛出的题，正式点，代码给全了。
