显然不弱于 bzoj2125 最短路。

先建出圆方树，圆方边按 bzoj2125 的方法建出来，这样两个圆点的最短路可以按 LCA 直接分类计算。

然后单组询问的时候，由于总点数被限制了，不难想到建立虚树。

建出虚树后在虚树上直接换根 dp 即可找出从每个子树到当前点的最长路，总复杂度 $O(n\log n)$，可以通过。

注意方点换根时需要一个单调队列。

参考代码。