CODE FESTIVAL 2017 Final J 题解

· · 题解

求完全图的最小生成树，立刻想到 Boruvka。

于是剩下的任务是，对于每个点 x，找到当前和它不在同一连通块的点 y 的 F(x, y) = w_y + dis_{x, y} 的最小值。

如果没有 x, y 所在连通块不同的限制，可以很轻易地换根 dp 完成。先自下而上求出 y 在子树内的 F(x, y) 最小值，再自上而下求出 y 在子树外 F(x, y) 最小值。

加上了这个限制，我们除了求每个 x 的 F(x, y) 最小值和它对应的 y，还要求次小值和它对应的 y。需要注意我们强制规定最小值和次小值对应的 y 当前所在连通块不同。这样如果 x 跟最小值的 y 在同一连通块，就可以让次小值递补。

时间复杂度 O(n \log n)。

code