arc167C
不会,看完题解感觉好妙,还是有很多不足。先对 ai 进行排序,容易发现排完序后并没有什么坏的影响,反而相当于少了一次映射。现在只要求出每条边的贡献即可,但是直接算贡献的话发现非常困难,这时可以考虑类似 kruskal 的思想,从小到大枚举到新的权值时,即在原图中加上一些这个权值的边,前面的边不受影响,所以可以求出权值 1-i 的会出现的边,与 1-i-1 的相减,这个是相对容易的。后面的组合是 n^2 算贡献,不算困难。
标签:原图,记录,题解,贡献,权值,一些,不错 From: https://www.cnblogs.com/Leonard7/p/17808077.html