庄严的棕树蛇 题解

思路

蛇长记为 $L=\operatorname{dist}(a,b)$。若某个顶点向三个互不相同的邻接方向都能延伸至少 $L$ 条边，则蛇一旦能完整驶入其中一条长支路，就能借助另外两条长支路调转方向。因此题面定义的枢纽正是能够完成掉头的场所；没有枢纽时答案一定为 NO。

剩下的问题是判断当前蛇能否到达任意枢纽。所有枢纽之间可以借助长支路互相到达，所以只需任取一个枢纽 $r$，把树以 $r$ 为根，判断蛇能否让两个端点变成祖先与后代关系。此时两端深度差为 $L$，整条蛇就在一条通向 $r$ 的根链上，随后一定能驶入枢纽并反转。

做法

第一次换根动态规划求出每个有向邻接方向能到达的最大深度。对顶点 $v$ 统计长度至少为 $L$ 的方向数，至少为三时它就是枢纽。

选定枢纽 $r$ 后重新定根，预处理：

• 每个顶点的深度与倍增祖先；
• 每个子树中深度最大的后代 $f_v$；
• 两点最近公共祖先。

设当前有向端点为 $(x,y)$。若两者深度差已经达到 $L$，因两者距离始终为 $L$，它们必为祖孙关系，答案为 YES。否则令 $p=\operatorname{LCA}(x,y)$，把 $x$ 沿其当前方向一直驶向最深后代 $f_x$：

• 若从 $p$ 到新 $x$ 的深度已经不少于 $L$，整条蛇可以落到同一根链上；
• 否则，利用倍增把另一端 $y$ 移到距 $p$ 恰为剩余长度的位置，然后交换两端角色并继续。

每轮至少耗尽一个此前尚未耗尽的下降方向，因此总轮数为 $O(n)$；每轮只做常数次倍增查询。

子任务 1 可把有序端点对 $(h,t)$ 作为状态，显式搜索所有距离为 $L$ 的蛇位置。子任务 2 中状态是树的有向边，只有树中存在度数至少为三的顶点时，非回退行走才能改变方向。子任务 3 的承诺保证：若存在枢纽，它已经在初始身体路径上，无需做完整可达性模拟。

正确性证明

在树中，蛇的每个位置都由有序端点唯一确定。一次操作等价于在一端接入一条不属于当前路径的边，并从另一端删除一条边，因此端点距离始终为 $L$。

若没有枢纽，任何顶点都不足以提供三条可容纳整条蛇的独立支路；蛇只能在至多两条长方向之间来回，无法把有向路径反转。若蛇完整进入某个枢纽的一条长支路，则可依次驶入第二、第三条长支路并反向驶回，故一定能反转。

以枢纽为根时，只要两端成为祖孙关系，整条蛇就位于通往枢纽的一条根链上，从而能够到达枢纽。模拟的一轮把一端推到当前子树最深处，这是该方向能够取得的最大进展；若仍不足 $L$，另一端的位置由保持端点距离 $L$ 唯一确定。于是该轮既不会遗漏可行移动，也会永久耗尽一个下降方向。若最终得到祖孙关系则可达枢纽；若所有方向耗尽仍未得到，则任何移动序列都不能到达枢纽。算法的判定因此与可反转性等价。

复杂度

每组数据的换根动态规划和模拟共需 $O(n\log n)$ 时间，空间复杂度为 $O(n\log n)$。