题解：P14362 [CSP-S 2025] 道路修复 / road（暂无数据）

唉，太失败了，204pts。

提供一个 $O(n2^k\alpha(n+k))$ 的做法。

给出一个结论：

回到本题，不妨枚举那些乡镇被城市化，问题变成一个最小生成树问题，已经有了个 $O((n\alpha(n+k)+(m+nk)\log (m+nk)2^k)$ 做法。

显然无法通过，如果对于原图运用上面的结论，$O(m)$ 边数会变成 $O(n)$，这是已经变成，再结合归并，我们得到 $O(2^k(\alpha(n+k)n+(nk+m)\log k))$，已经很优秀了，卡卡常该过。

但是，我们还能更加简化，不妨考虑把每个情况的考虑边数变成 $O(n)$ 的具体地，我们还是沿用上述结论，不妨考虑扔掉一个乡镇，剩下的边集得到的最小生成树是被处理出来过的，这是在加上这个乡镇的话又多了若干条边，由于上述结论，只有剩下的边集得到的最小生成树和多出来的边是有用的，归并后跑最小生成树即可。