LG CF1184E3 Daleks' Invasion (hard)

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转题意: 给一颗树,每条边权值可以修改为$x$,使得修改后这条边可以在最小生成树上,问$x$最大可以是多少?首先求出最小生成树(以下的树指最小生成树)修改一条边时,若不是最小生成树上的边,则为树上该边两端节点之间的最大值若是树上的边,那么就是该边子树中找出一些非树边(使它们最大值尽可能小)连接除子树部分的点,答案为该边权值看上去不是很好处理我们将非树边按权值从小到大排序,从下往上合并,用并查集维护即可每次遇到非树边$x,y$时,就更新并合并$x\to \text{lca}{x,……