考虑随机对图进行二染色，使得路径上恰好连续 $\left\lfloor\frac k2\right\rfloor$ 个点颜色是白色，剩下点是黑色。这样的概率约为 $\frac{k}{2^k}$，故随机 $O(\frac{2^k}{k}\log \frac1\varepsilon)$ 次就能使得错误率小于 $\varepsilon$。剩下的问题是只考虑同色点，求出两两点对之间长度为 $0,1,2,3,4$ 的最长简单路。

• 长度为 $\le 1$ 的情况是平凡的。
• 长度为 $2$，只需枚举中间的点的两条邻边。
• 长度为 $3$，只需枚举两条顶点不相交的边，更新 4 个点对的答案。
• 长度为 $4$，不妨设为 $u_0,u_1,\ldots,u_4$，先用上面的方法求出 $u_1$ 和 $u_3$ 之间的长度为 $2$ 的前三长路，然后枚举两条顶点不相交的边，即 $(u_0,u_1)$ 和 $(u_3,u_4)$，找到 $u_1$ 和 $u_3$ 之间不经过 $u_0$ 和 $u_4$ 的最长路即可。

每次的复杂度为 $O((n+m)^2)$，故总复杂度 $O((n+m)^2\frac{2^k}k\log\frac1\varepsilon)$。