根号分治.
先预处理倍增数组用于支持查询 LCA, 预处理和查询 LCA 的时间复杂度为 $O(n\log n + m\log n)$ .
$k\le \sqrt n$
预处理出 $nxt(x,i)$ 表示从 $x$ 向上跳 $i$ 步走到的点, $sum(x,i)$ 表示从 $x$ 向上每次跳 $i$ 步经过的点权和.
于是询问时就可以做到 $O(1)$ 回答.
这部分的时间复杂度为 $O(m\sqrt n)$ .
$k> \sqrt n$
对于 $k>\sqrt n$ 的询问,显然跳的步数不会超过 $\sqrt n$ ,每次用倍增找出要跳到的下一个点,更新答案即可.
这部分的时间复杂度为 $O(m\sqrt n\log n)$ .
适当调整
可以发现,若我们对 $k\le b,k>b$ 分别执行以上两种算法,两部分总时间复杂度为 $O(mb+m\frac n b\cdot \log n)$ .
取 $b=\sqrt {n\log n}$ 即可做到 $O(m\sqrt{n\log n})$ ,再算上求 LCA 部分,复杂度为 $O(m\sqrt {n\log n}+(m+n)\log n)$ .
然而这只是理论复杂度,实现时由于常数等原因需要自己调节参数以取得更好的效果…
1 | //%std |