显然有一个 $\mathcal O(m\log m)$ 的 LCT 做法：将边按照 $a$ 升序排序，依次加入，动态维护最小生成树，这是 LCT 的经典应用。

那我不会 LCT，又该怎么通过这个题呢？

令人疑惑的是，榜上有大量的神秘复杂度 SPFA 做法，还有评论区中的二分套二分。这显然是错的，事实上不会 LCT 也有对应的常规手段处理。

秉持着 "直接做就好了" 的信念来处理，考虑二分答案转化为判定问题，设二分值为 $mid$。我们要求 $a_{\max} + b_{\max} \le mid$，不好利用判定的优势，于是转化一下，令 $c = mid - b$，那么就是 $a_{\max}\le c_{\min}$。

这个限制可以改写成 $\forall (a, c), a\le c_{\min}\le c$。此时就比较明晰了，使用线段树分治 + 可撤销并查集维护每个 $c_{\min}$ 对应的边，判断是否能形成一棵生成树，如果可行便 check 成功，如果不存在这样的 $c$ 则 check 失败。

时间复杂度 $\mathcal O(m\log^2 m\log n)$。代码也比较好写。

冷静下来想想，这个做法其实是有一些道理的（接下来是自己的碎碎念，并不一定很有意义）。

由 [SDOI2008] 洞穴勘测 我们知道，对于简单的，只含边的加入 / 撤销，判断联通状态，可离线的 LCT 问题，我们可以采用线段树分治 + 可撤销并查集来维护。结合 LCT 维护最小生成树的背景，猜想可以通过一些转化，让条件变成形如 "一条边有少数个存在的范围，判断是否能形成一棵生成树" 这样的问题。

一开始的一些推断告诉我们，直接做不存在好的数学性质，并且只能 LCT 维护，进而想到尝试二分答案转化为相对容易的判定。通过常见手段对限制进行改写，从而使得判定条件中的常数 $mid$ 带来更多作用。结合前面的感觉，得到正确的解法。

COGS 的 G++9.30 评测机还没有好。。。代码就放在 这里 了。由于卡常，代码并不是很可读。