这篇 目前应该是题解区里的第七篇
此题解
每一条树边我们维护一个权值,表示能更新它的非树边的最小值
同时题解利用并查集将已经被更新过的树边删掉。
我们可以构造出如下的一种hack数据
in: 5 6 1 2 1 2 3 1 3 4 1 4 5 1 1 5 1 4 5 2
ans: 5
最小生成树为一条链,链上的边权相同,且最小的非树边连接了链首与链尾,与链上边权都相同,这篇题解的做法会直接将所有边删除,但由于边权相同无法得到严格次小生成树。不清楚为啥数据能放过去