假设把 $2q$ 条特殊边合并，然后再跑一遍最小生成树，那么在这棵树上的非特殊边不管选了哪些特殊边都在最小生成树上。
我们把这些边合并之后就只剩下 $O(q)$ 个连通块，所以也只有 $O(q)$ 条非特殊边（还是只有最小生成树上的边有用）。
枚举每一对特殊边当中选哪条，然后跑最小生成树即可。时间复杂度 $O(m\log m+2^qq)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #284 for Problem #7069. Farm
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 06:51:59
Last updated: 2025-12-14 06:52:03
题解
Comments
No comments yet.