洛谷4949 - 最短距离

本题大概是一个基环树上带修改边权的最短距离。可以把他看做一棵树,把多的那条边拎出来,树剖维护距离,分类讨论即可。大概是你谷蓝题难度吧。

由于树剖只需要查询 dfs 序上区间最小值,可以考虑树状数组维护常熟较小。目前不卡常的情况下你谷效率 rk1 。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×