考虑对 做根号分治,设阈值为 。 若 ,则这样的询问不超过 个,直接从 出发做一遍拓扑 dp,求出所有能到达点的最长路,再找到不在讨厌集合里最长的即可。 若 ,对每个点预处理出最长路前 长的点,查询时要么 能到达的点数不超过 个,要么前 长的点中至少有一个不在讨厌集合里,找到最长的那个即可。 实现的比较垃圾,预处理的时候带了个排序,所以 应该小于 来降低预处理的复杂度,调参了个 200 卡过去了。(也可能是牛客机子抖 code