HRBUST 1849 商品中心

vjudge

智商掉线...

可以发现一条边能贡献其他点当且仅当两点路径上这个边权值最小,所以如果按照边权从大到小加边,每加一条边就会合并两个联通块,那么一个联通块内的点到另一个联通块的点的权值就都是那条边的边权,所以可以给两个联通块内的点答案分别加上边权可以发现一条边能贡献其他点当且仅当两点路径上这个边权值最小