AT_cf17_final_j 题解

题意

给定一棵既有点权也有边权的树，构造一个完全图，图中两点间边的边权为树中两点点权之和加上两点间的距离，求该图的最小生成树。

思路

发现完全图总边数太大，考虑减少边数。

这里有一个性质：

如果在一个图中选取任意个联通的边集，使得它们的并为全集，则整个图的最小生成树中的边一定在 分割后的两个边集的最小生成树中出现。

证明：

假设有一条边 \((u,v)\) 在全图的最小生成树中却不在分割后的边集中，那么在包含 \((u,v)\) 的边集中一定存在一条连接 \((u,v)\) 的链，而这一定不比 \((u,v)\) 劣，否则 \((u,v)\) 一定可以替换这条链中的某一条边而成为最小生成树的一部分。

考虑优化建边：对于树上每个点，我们要让在新图中的包含这个点的边期望不超过 \(O(\log n)\) 条，才能够求整个图的最小生成树。

记 \(u\) 的点权为 \(w_u\)，\(u\) 和 \(v\) 在树上的距离为 \(dis_{u,v}\)

那么 \(u\) 和 \(v\) 在完全图中的边权就为 \(w_u + w_v + dis_{u,v}\)。

发现这个式子不是很对称，考虑把 \(dis_{u,v}\) 拆了。

考虑从最近公共祖先处拆，此时这个式子可以写成 \(w_u + dis_{u,lca} + w_v + dis_{v,lca}\)，最小生成树显然是从 \(w_u + dis_{u,lca}\) 最小的 \(u\) 连向其他点，至于两个点在同一个子树内的情况，则会在该子树中算出更小的边权，不会影响答案。

但这样最坏复杂度还是 \(O(n^2)\) 的，考虑换个位置差：点分树上最近公共祖先，这样复杂度就是 \(O(n\log n)\) 的。

所以最终做法为：跑点分治，对于每个子树建完边后跑一边最小生成树即可。