做到 $CF$ 上有一道题。 大概题意是给定一张带权图，其中第一条边的边权待定，要使得这条边在 $MST$ （最小生成树）内，其边权最大可以取多少。

大概思路是，定义第一条边链接 $u$ 和 $v$ 两个点，那么当其权值无限小的时候，按照 $kruskal$ 算法就一定会选择这条边。此时尝试贪心地调大边权，当第一条能够链接 $u$ 和 $v$ 所在集合的边 $E$ 出现的时候，其权值就是第一条边的最大取值，否则则能够用 $E$ 来替代第一条边使得答案更优。

题目挺水的，但是我还有个想法。 假设第一条边不存在，正常跑个 $MST$ 出来，此时若将第一条边加入图中，必定会形成一个环（记为 $G$），那么只要第一条边的边权满足 $w\le \max_{i\in G}{ w_i}$，就能够被替换到最小生成树中。 所以我猜测这两种算法应该是等价的。

想了一下， $u$ 到 $v$ 路径上第一条能够连接 $u$ 和 $v$ 集合的边一定是最后枚举到的，也就是该路径上权值最大的。

请问大佬们，这个结论正确吗？