草稿:
非树边 \(u,v,[l,r]\) 把 \(u,v\) 路径上所有边上界与 \(r-1\) 取个 \(\min\)。
剩下的边左端点排序后贪心,每次取右端点最小的一个元素。开始只考虑树边。
当前加入一个树边后,如果某条非树边 \(u,v\) 的路径形成,把它纳入考虑范围,修改它的下界?
为什么是对的?
我们肯定希望树边的权值尽量小。所以先考虑树边然后尽量压榨非树边就非常的优?
哦我是傻逼显然正确
标签:eJOI2022,loj3885,树边,Tree,Bounded,Spanning,非树边 From: https://www.cnblogs.com/stinger/p/16817271.html