English version
Hints
How to choose the edges greedily?
In which cases does the greedy method fail?
How can we find the extra non-tree edges?
Solution
Step1
First, sort the edges by weight.
If the first $$$n-1$$$ edges don't form a tree, they already form the minimum spanning tree (MST) -- that's the answer.
Step2
If the first $$$n-1$$$ edges form a tree,consider adding a extra edge with weight $$$w$$$ outside the tree that creates a cycle. Remove a edge with weight $$$w_0$$$ from the tree, keeping the cycle, increasing the answer by $$$w-w_0$$$.
The problem reduces to finding the maximum weight of the edge outside path $$$(u,v)$$$ (i.e. $$$\max\limits_{e\in E,e\not \in path(u,v)}w(e)$$$).
This can be done efficiently using binary lifting, taking care of corner cases at the LCA (Lowest Common Ancestor).
Step3
If more than $$$2$$$ edges are removed from the tree, we can show that replace $$$e_{n-1},e_{n-2}$$$ with $$$e_{n+1},e_{n}$$$ is the case to consider.
Step4
Putting everything together, we obtain a $$$O(n\log n)$$$ approach, which is efficient and clean.
Code
Reference
Codeforces Round 1069 Editorial
中文版本
Hints
如何贪心地选择边？
贪心方法在哪些情况下会失败？
我们如何找到额外的非树边？
Step1
首先，按权重对边进行排序。
如果前 $$$n-1$$$ 条边不构成一棵树，那么它们已经构成了最小生成树（MST）——这就是答案。
Step2
如果前 $$$n-1$$$ 条边构成了一棵树，考虑添加一条权重为 $$$w$$$ 的树外额外边，这会创建一个环。从树中移除一条权重为 $$$w_0$$$ 的边，同时保留环结构，使得答案增加 $w — w_0$。
问题转化为寻找路径 $$$(u, v)$$$ 外部的边的最大权重（即 $\max\limits_{e \in E, e \notin \text{path}(u,v)} w(e)$）。
这可以通过使用**树上倍增**来高效完成，并注意 LCA 处的边界情况。
Step3
如果从树中移除超过 $$$2$$$ 条边，我们可以考虑用 $$$e_{n+1}$$$ 和 $$$e_n$$$ 替换 $$$e_{n-1}$$$ 和 $$$e_{n-2}$$$ 的情况。
Step4
将所有部分结合起来，我们得到了一个 $$$O(n \log n)$$$ 的方法，该方法高效且清晰。
Comments (0)
