网站首页
编程语言
数据库
系统相关
其他分享
编程问答
abc355f
2024-06-06
abc355f 题解
abc355f直接贺lct维护mst的代码。思路观察到\(w_i\le10\),考虑分开建\(10\)个图表示边权小于等于\(i\)的边组成的图。连并查集,记录当前图连了\(siz_i\)条边。可以发现第\(i-1\)个图是第\(i\)个图的子图。所以差分\(siz_i-siz_{i-1}\)可以得到原图的最小生成