两枚棋子 题解

思路

将距离约束转化为对方必须访问的第 $d$ 级祖先，再统计两枚棋子的根连通闭包。

做法

子任务 1：状态图最短路

当 $n\le8$ 时，状态可记录两枚棋子的位置及各自已经访问的必经点集合。枚举移动其中一枚棋子的所有合法转移并做 BFS，首次回到根且完成两个集合即为最优答案。

子任务 2：根端链

设两枚棋子各自最深的必经点深度为 $x,y$。为了保持距离限制，第一枚棋子还必须到达深度 $\max(0,y-d)$，第二枚棋子还必须到达 $\max(0,x-d)$。链上访问一个最深点并回根的代价是其深度两倍，答案为

子任务 3：祖先补点与树上闭包

对 $A$ 中每个节点 $x$，把 $x$ 的第 $d$ 级祖先加入第二枚棋子的必经集合；对 $B$ 对称处理。随后分别把两个必经集合向根传播。某枚棋子的闭包中每个非根节点对应一条必须往返经过的父边，因此答案是两个闭包内非根节点数量之和的两倍。

第 $d$ 级祖先用倍增求出，闭包按 DFS 序的逆序传播。

正确性证明

引理 1 若第一枚棋子访问 $x$，第二枚棋子必定访问从 $x$ 向根最多上移 $d$ 条边得到的祖先。

证明 第一枚棋子首次到达 $x$ 时，第二枚棋子与它距离不超过 $d$。第二枚棋子从根侧进入 $x$ 所在子树时必经过该祖先；若始终未进入该祖先以下，则距离会超过 $d$。∎

引理 2 补入对方的第 $d$ 级祖先后，两枚棋子分别遍历各自必经点的最小根连通子树即可满足距离限制。

证明 按两个闭包节点合并后的 DFS 次序访问；一枚棋子的下一步会使距离超过 $d$ 时，让另一枚棋子沿其闭包向前一步。补点保证所有这些跟随边已经属于另一枚棋子的最小子树，不产生额外移动。∎

定理 算法输出最少操作次数。

证明 由引理 1，所有补点及其根路径都是任何合法方案必须经过的边，每条边还必须往返，构成下界。由引理 2，存在恰好遍历这些边两次的合法方案，达到该下界。∎

复杂度

暴力状态 BFS 的状态数为 $O(n^2 2^{2n})$。链上算法为 $O(n)$。满分算法使用倍增，时间复杂度 $O(n\log n)$，空间复杂度 $O(n\log n)$。