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
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)\) 的方法，该方法高效且清晰。
代码
Code
参考
Codeforces Round 1069 题解