题目链接：

http://codeforces.com/problemset/problem/733/F

题意：

给定无向图及图上每条边的$value$和$cost$值，花费$cost$可以使$value-1$，$value$可以减为负数。现给定预算$k$，让你从图中找到一棵生成树，使得花光预算后树上边的$value$和最小。

分析：

题目要求使预算和最小且$value$可以减到负数，所以我们必然要将预算全部花费在树上$cost$值最小的边上。
首先求个最小生成树，
考虑树上的边，选择$cost$最小的边，直接计算。
考虑非树上的边，选择$cost$比树上最小$cost$小的边，加入该边后形成一个环，删除到环上$value$值最大的那条边，这个过程直接在树上倍增求个LCA就可以解决，最后统计答案时再把我们选的这条边加上去。
两种情况下的最小值即为答案。

代码：

1
2