查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转仔细考虑一下,最终能够形成最小权值的生成树的情况一定是把 S 都用在减小某条边的费用如果那条边在最小生成树上,那么直接处理即可如果在外面,设这条边为$x \rightarrow y$,我们求出最小生成树上$x$到$y$上最大的一条边,删掉这条边枚举删掉哪条边,然后执行上面的操作就可以了记得开$long\ long$,$rmq$的数组开大点……