用 记录 的 入序和出序，就可以 判断 是不是 的祖先。

在找 的时候就可以只跳一个点。

注：需先设定

习题：

#10131. 「一本通 4.4 例 2」暗的连锁

掉附加边不会影响原图的连通性，所以分成哪两部分取决于去掉树上的哪条边。

我们枚举去掉树上的哪条边，如果这条边去掉后分成的两部分只有小于一条附加边连着，就可。

所以对每一条附加边连接的 ，我们将他们俩路上的边权加一，就知道哪条边被附加边强连接了多少次了。

树上差分即可解决。

#10132. 「一本通 4.4 例 3」异象石

每加入一个节点，它对于答案的贡献是

其中 为树上距离， 为前驱， 为后继。

相应地，删除一个节点的贡献为

注意： 这样计算出的答案是题目所求的两倍，故询问要除以2。

#10133. 「一本通 4.4 例 4」次小生成树

先求最小生成树，然后枚举剩余的 条边，试图加进来。

加进来自然变成一条环，考虑在这条环上去掉一个最大的边。

用 更新答案最小值即可。

需要注意 的情况，因为求的是严格次小生成树，故需要记录一下环中的严格次小边，尝试用 来更新。

#10136. 「一本通 4.4 练习 3」聚会

记 两两的 为 ，
则 中有两个相同，答案就是不同的那个，也就是 x^y^z

画图理解一下

又从 刚好走了答案的两倍，故答案就是

#10137. 「一本通 4.4 练习 4」跳跳棋

把每个状态看成树上的一个结点，两边向中间跳是向父亲走，中间向两边跳是向两个儿子跳。

问题转化为判断两个结点的根是否相同，所需方案就是树上距离。

可以先通过倍增求出结点到根的距离与根状态。

然后若两个状态根结点一样，就先跳至同一高度，再向上倍增，求 。

关于向上跳的操作，例如 ，为了优化，我们就可以一次性跳到 。