AT_cf17_final_j Tree MST

发表于 分类于 ， ， 阅读次数：

题意 : 给定一棵 个点的树 ，边有边权，点有点权 。

建立一张完全图 ， 之间的边长为

求完全图的最小生成树边权和。

，时限 。

算法一

  • 结论：欲求边集 的最大权值生成森林，可以先将 划分为两部分 ，分别求出两者的最大权值生成森林，，再求 的最大生成森林即可。

    用 Kruskal（拟阵的性质）容易证明。

点分治，每次考虑跨越重心的路径所生成的边集。

以分治中心为根，令，则连接两个点的代价就是 。

我们只需保留 最小的一个点，然后把其他点都和它相连，显然就是 MST 了。

这里会产生子树内自己连的路径，但是比直接连劣所以不会影响答案。

点分治一共会产生 条边，然后跑一个 Kruskal 就 。

算法二

完全图 MST，考虑使用 Boruvka 算法。

每一轮，我们要对每个连通块找到到达其他连通块的最小出边。

对于一个已经联通块染色的局面，我们可以在 上进行 up and down DP。

对于点 ，记 表示 子树内 最小的 ，它是最优的目的点。然而，我们还有颜色不同的限制，只需要记录最小值和次小值（颜色必须和最小值不同），这样万一最小的颜色相同，还有补刀的。

以上计算了下方的共线，再次 dfs 计算从上面延伸过来的贡献即可。

每轮会使连通块个数减半，复杂度 ，常数较大。