bzoj 1977: [BeiJing2010组队]次小生成树 Tree 树上倍增+kruskal

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1977


先跑出来最小生成树

然后枚举不在树上的边

添加这个边之后,需要把形成的环上的一条边拆掉

由于需要严格次小,所以维护一下最大值和次大值

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注