[NowCoder11253L]WeChat Walk

设 $deg>B$ 的为大点， $deg\le B$ 的为小点。由于总步数 $w\le10^4$ 且每个人的步数是与时间正相关的，考虑按步数 $w$ 从大到小枚举，设 $u$ 在 $t$ 时刻走到步数 $w$ ， $u$ 是冠军当且仅当 $u$ 相邻的点在之前没有更新过步数或者更新的时刻大于 $t$ ，设 $f_u$ 表示 $u$ 最近一次更新步数的时刻， $las_u$ 表示 $u$ 上一次更新步数的时刻，初值均为最终时刻 $q$ 。
故 $u$ 保持步数为 $w$ 且为冠军的持续时间为 $\displaystyle \max\{t,\min(las_u,\min_{(u,v)\in G}f_v)\}-t$ ，若 $u$ 为小点则 $\displaystyle \min_{(u,v)\in G}f_v$ 可以暴力计算，若 $u$ 为大点，考虑直接维护这个结果（记为 $mn_u$ ），即每个点步数更新时，枚举其周围所有大点 $v$ 来更新 $mn_v$ 。由于大点数量 $<\displaystyle \frac mB$ ，故总复杂度为 $\displaystyle O(W+qB+q\frac mB)$ ，取 $B=\sqrt m$ 即可。时间复杂度 $O(W+q\sqrt m)$

代码