CODE FESTIVAL 2017 Final J 题解

problem & blog。

萌萌点分治，积累个 trick /qq。

对于完全图 \((V,E)\)，将 \(E\) 分成 \(E_1, E_2, \cdots, E_k\)（\(E_1 \cup E_2 \cup \cdots \cup E_k = E\)）。对每个边集求 MST，得到新边集 \(E_1^{'}, E_2^{'}, \cdots, E_k^{'}\)，再求 MST。最终剩下的边集，等同于原边集的 MST。

反证是平凡的，就不证了。

对照上面那玩意，\(E_i\) 是可以随便选的，所以直接上点分治。对于一个中心，按照板子求遍 \(dis_u\)。那么 \((u,v)=w_u+w_v+dis_{u,v}=(w_u+dis_u)+(w_v+dis_v)\)。故可以按照 \(w_u+dis_u\) 为关键字，取其中最小的那个，和同一次 divide 时获得的其他 \(u\) 组合边。

按照 trick 的理论，跑遍 Kruskal 就是答案了。

所以甚至比洛谷模板题还好写。

代码，看起来是两只 log 的，不是很会证这种东西所以不管了。