找出图的任意一个 DFS 树。有一个跨过 $i$ 的返祖边就代表 $i$ 在一个简单环中，故跨过每个点的返祖边的个数都 $\leq k$。

对 DFS 树点分治。设当前分治中心为 $u$，当前点集被 DFS 树分成了若干子树。两个点的最短路要么经过分治中心 $u$，要么经过「跨过 $u$ 的反祖边的端点」，要么这两个点在同一个子树中，且最短路没有出这个子树（即分治子问题）。对于前两种情况，在点分治时对于以上的 $O(k)$ 个点分别求出最短路 $d$，询问时用 $d_u+d_v$ 作为 $(u,v)$ 的最短路更新答案。