9.16
上午补了一下暑假姚子奇讲的题，让姚子奇给我调个题他都不带鸟我的。
先用kruskal将最小生成树求出来，之后再枚举不在最小生成树的每条边，设每条边的端点为x, y，如果加入这条边，则会形成一个环，于是我们考虑用这条边替换x和y路径上的一条边，但是由于是要求次小生成树，所以我们要替换路径上边权最大的边，我们可以用倍增来维护，每次求的时候分别求出x到lca的最大值和y到lca的最大值即可，但是会出现一个问题，如果当前枚举的这条边的边权和最大边权一样怎么办，于是我们还要维护一个次大值，也是用倍增维护即可，于是当当前边的边权和最大边权一样时，我们就将次大值替换掉即可，于是我们就可以将这道题切了。
剩下的提明天再写，没时间了
标签：总结,每日,替换,生成,lca,条边,姚子,边权 From： https://www.cnblogs.com/pooletea/p/18416670