NOID1T归程

时隔一个月左右更新一下博客...

看到这题很容易想到反向SPFA,然后可持久并查集搞搞啥的。

(离线那分显然是送的。。。

但是该题会卡SPFA(貌似),且可持久化并查集我的时间复杂O(n log^2 n)

所以光荣的只拿了60分滚粗qaq...

上面算法又臭又难写...想想正解...

实际发现按照边排序后因为每次合并的时候边的高度一定降低。

那么考虑维护一颗并查集树,每个节点记录这里面点的最低高度,以及最近距离。

那么答案就是询问点能向上访问的最高节点记录的最近距离...代码异常简洁明了...

可持久化并查集代码如下:

满分代码如下:

 

2 + 2 =