神仙数据结构题。

:::info[树上圆定理]{open} 考虑以树上某个点为中心，将距离它不超过 $k$ 的点作为一个点集，我们称这个点集为树上的圆，称该点为圆的圆心，称该圆半径为 $k$。

考虑两个相交的树上圆，注意到它们的交集也一定是一个圆，且其圆心一定位于二圆心连线的中点。证明不难，故略。 :::

你注意到主要难点在于注意到这个定理与观察到可合并性。

:::info[合并]{open} 考虑去维护当前人可能在的位置。 如果当前操作下，人一步都不用动，我们就维护出一步不用动的点集。注意到所有宝石都是树上圆，直接维护圆即可。

人若动了，那么从初始圆出发，经过每个圆最终进入最终圆的最短路径是唯一的，可以记录下初始出发点与最终抵达点，以及中间走过的路程。

显然，只有未动与未动的合并较为复杂。

1. 两个树上圆相离，那么无论如何都会动。求出二圆心最短路径与两个圆分别的交点作为出发点与抵达点，路程即为二点距离。
2. 两个树上圆相交，直接合并即可。 :::

然后就可以轻松口胡出一个线段树的 $O(q\log^2n)$ 做法，然后你会惊喜地发现自己 TLE 飞了。

是的，毒瘤的出题人把线段树卡掉了，考虑优化掉查询的一层 $\log$。

注意到，有一种热门离线数据结构叫猫树，思路非常自然，复杂度 $O(n\log n) - O(1)$。于是你改成了猫树，惊喜地发现自己又 TLE 飞了。

注意到，有一种东西叫长链剖分，它可以帮助我们在 $O(n\log n) - O(1)$ 求出树上 $k$ 级祖先；注意到，有一种东西叫欧拉序与 ST 表，它可以帮助我们在 $O(n\log n) - O(1)$ 求出 LCA。

然后你惊喜地发现复杂度变成了 $O(q\log n + m)$，然后你就会惊喜地发现自己过了。

AC 代码。

笑点解析：长链剖分常数实在太大了，你把它换成倍增尽管复杂度更劣，但跑得更快。