CF827D Best Edge Weight（MST/倍增/树上并查集）

· · 题解

第一届粉兔杯被粉兔用这道题淘汰话说粉兔杯怎么出原题啊。

先随便找出一棵生成树，对于树边和非树边分别计算答案。

非树边 (u,v) 的答案为 u,v 在树上路径权值 \max-1，这里我使用倍增求。

树边的答案为所有覆盖其的非树边的权值 \min-1（没被覆盖过则答案为 -1），这里将非树边按边权升序排序，一条链覆盖前面覆盖过的树边是无意义的，所以使用树上并查集维护没有被覆盖过的边即可。

复杂度线性对数。

代码 挺短的。