cnyz's Blog

Kruskal 重构树，即为在 Kruskal 求生成树过程做一小点的修改，将边权作为一个新点的点权，并作为这两个点祖先的的父亲。

那么，我们可以把一张无向图转化为一棵树，就可以配合倍增做一些神奇的操作了。

这棵树甚至还有一些神奇的性质。

1. 是一个二叉树。
2. 如果是按最小生成树建立的话是一个大根堆。
3. 任意两个点路径上边权的最大值为它们的LCA的点权。

时间复杂度是 $O(n\log n)$ 的。

NOI 2018 归程 Return Journey

先使用最短路求出每个点到 $1$ 号点的最短距离。

然后，根据海拔做 Kruskal 重构树，在重构树上 DFS 求出从一个点到 $1$ 号点的最短距离。

然后对于每一个询问 $(x,y)$，倍增求出可以跳到最高的点位。

时间复杂度 $O(m\log n+q\log n)$。

IOI 2018 狼人 Werewolf

根据 $\max(i,j)$ 与 $\min(i,j)$ 建重构树，原问题就变成了，在 $A$ 树上求出 $S$ 能够在 $v_x\ge L$ 能跳多远，在 $B$ 树上求出 $T$ 能够在 $v_x\le R$ 能跳多远。

然后二维数点即可。