这题数据好像有点水
查看原帖
这题数据好像有点水
215915
lOpzIth楼主2022/10/6 21:57

想到一个假做法,先对于每次询问都用树剖跑好LCA和两点之间的距离(先没有虫洞),然后按照距离为第一关键字排序每一次询问,然后枚举每一条边,每一次询问,如果当前边在询问的点之间就暂时性减去,(每次做完后判断当前值是否比后一个大,若大于等于,则当前值一定为此次操作的最大值,退出即可,若小于,则继续跑)(优化),每次将最大值与ans取min,这样的时间复杂度应该是O(nm)O(nm) ,但好像这个做法没有卡,直接水过了,但是若不加这个小小的优化,直接T麻了,60pts。不是很懂这个写法的正确性,有人能说明一下么QAQ

2022/10/6 21:57
加载中...