两道题我都不知道有没有更优做法。。

https://daniu.luogu.org/problem/show?pid=3591

如果步长>根号的话，

步数就<根号，

直接暴力模拟每一步就可以了。

如何暴力模拟？

求出lca，问题就只剩下如何求一个点距离为k的祖先。

就是按size链剖，每条链记录每个深度的点。

找距离为k的祖先，如果当前这条链不够，就跳到下一条链。

这样最多一次询问只会跳log条链，时间是根号的。

(其实这个问题17年集训队论文里讲了梯子+倍增的O(1)做法，不过这题我这样做也就已经均摊O(1)了)

如果步长<根号的话，

我们就对每个这样的步长k特殊处理，那么也只用处理根号次。

就是dp出每个点距离为k的祖先，并处理出i,i-k,i-k*2...点权的前缀和。

询问时找到最浅那个i-k*x就可以了。

dp时间也是n根号的。

总时间n根号。

https://www.luogu.org/problem/show?pid=3751

对每个询问暴力模拟，时间应该是k[x]+k[y]的。

也就是每次选一个离下一个点较近的移动，之后判一下是不是起点的相对前后!=终点的相对前后。

如果k[x],k[y]都<根号，那么这是没问题的。

如果k[x],k[y]都>根号，那么记忆化一下，应该也是没问题的。

否则，如果我们能用较小的k的时间，那么也是ok的。

因为速度是一样的，所以x移动一次最多只会相遇一次，而且相对前后一旦变了就变不回去了。

所以只要每次移动x，之后二分一下y会移动到哪里就可以了。

时间O(n根号log)