CF1108F MST Unification

很丁真的一个题，权当复习下树上倍增的写法了 考虑先给图求出一个MST，那么很容易发现对于每条非树边\((u,v)\)，它的权值必须严格大于MST上\(u,v\)之间所有边的权值，否则就可以用这条非树边来替换某一条树边 因此直接倍增维护树上两点间最大边权即可，复杂度\(O(n\log n)\) #in
posted @ 2023-10-16 18:16  空気力学の詩  阅读(9)  评论(0)  编辑  收藏  举报