题解：图上的追逐游戏与最迟行动时间计算

---

问题分析

本题是一个在无向图上的追逐游戏：

• 两个玩家：007（守方）和 Dr. Null（攻方）
• 目标：Dr. Null 想摧毁服务器，007 想阻止他
• 移动规则：轮流行动，每步可移动到相邻节点或停留
• 特殊规则：服务器 $a$ 和 $b$ 相邻，摧毁需要 1 单位时间
• 007 胜利条件：
  1. 抓住 Dr. Null（同节点）
  2. 保证 Dr. Null 永远无法摧毁服务器

我们需要计算 007 最多可以延迟多少回合开始行动（即吃早餐时间），仍能保证必胜。

---

关键观察

1. 服务器位置的重要性

由于两台服务器相邻，Dr. Null 要摧毁服务器，必须到达 $a$ 或 $b$，然后花费 1 回合摧毁。这给了 007 额外的反应时间。

2. 距离差分析

设：

• $dist_a(u)$：节点 $u$ 到服务器 $a$ 的最短距离
• $dist_b(u)$：节点 $u$ 到服务器 $b$ 的最短距离

对于初始位置：

• 007 在 $s$，Dr. Null 在 $d$
• $x = dist_a(d) - dist_a(s)$：Dr. Null 到 $a$ 的距离领先
• $y = dist_b(d) - dist_b(s)$：Dr. Null 到 $b$ 的距离领先

3. 胜负初步判断

• 如果 $x < 0$ 或 $y < 0$：007 到某个服务器比 Dr. Null 更近，可直接防守
• 如果 $x \neq y$：007 可以专注于防守较近的服务器
• 如果 $x = y \ge 0$：情况复杂，需要进一步分析

---

算法框架

第一步：计算距离

1. 从服务器 $a$ 出发 BFS，计算所有节点到 $a$ 的最短距离 $book[]$
2. 从服务器 $b$ 出发 BFS，计算所有节点到 $b$ 的最短距离 $book2[]$

第二步：初步判断

计算：

• $x = book[d] - book[s]$
• $y = book2[d] - book2[s]$

如果 $x < 0$ 或 $y < 0$ 或 $x \neq y$：

• 答案 = $\max(-1, \min(x, y))$
• 这是因为 007 可以等待 $\min(x, y)$ 回合再行动

第三步：复杂情况分析

当 $x = y \ge 0$ 时，需要更精细的分析。

核心思想：在 $x = y$ 的情况下，Dr. Null 可以威胁两个服务器。007 需要判断能否同时防守两个方向。

定义：

• 安全路径：一条路径，满足沿路径移动时，到两个服务器的距离差保持不变
• 最长安全路径：从起点出发，沿安全路径能走的最远距离

第四步：计算最长安全路径

1. 从 $s$ 出发 DFS，只走满足 $book[v] < book[u]$ 且 $book2[v] < book2[u]$ 的边
   • 这保证了沿路径移动时，到两个服务器的距离都在减少
   • 且距离差 $book[u]-book2[u]$ 保持不变（等于初始差）
2. 记录从 $s$ 出发的最长路径长度 $max1$
3. 同样从 $d$ 出发计算 $max2$

第五步：最终判断

如果 $max1 + x \ge max2$：

• 007 可以在等待 $x$ 回合后行动并获胜
• 答案 = $x$

否则：

• 007 需要提前 1 回合行动
• 答案 = $x - 1$

---

正确性证明

为什么考虑 $x = y$ 的情况？

当 $x = y$ 时，Dr. Null 到两个服务器的领先距离相同。他可以灵活选择攻击哪个服务器，迫使 007 分心防守。

最长安全路径的意义

• $max1$：007 从起点能沿"同时靠近两个服务器"的路径走多远
• $max2$：Dr. Null 从起点能沿同样性质的路径走多远
• 如果 $max1 + x \ge max2$，说明 007 即使等待 $x$ 回合，仍能追上 Dr. Null 在这种特殊路径上的进展

边界情况

• 当 $x < 0$：007 更接近服务器，可以直接防守
• 当 $x = y = 0$：双方到服务器距离相同，007 需要立即行动
• 当无法获胜时：输出 $-1$

---

复杂度分析

• 时间复杂度：$O(n + m)$
  • 两次 BFS：$O(n + m)$
  • 两次 DFS：$O(n + m)$
• 空间复杂度：$O(n + m)$

对于 $n \le 2\times 10^5, m \le 6\times 10^5$ 完全可行。

---

总结

本题是一道图上博弈与距离分析的综合题目，主要考察：

1. 问题转化能力：将追逐游戏转化为距离差分析
2. BFS/DFS应用：高效计算最短距离和特殊路径
3. 博弈分析：理解回合制移动对胜负的影响
4. 特殊情况处理：处理 $x = y$ 时的复杂情况

算法的核心洞见在于：

• 利用服务器相邻的特性简化防守分析
• 通过距离差初步判断胜负
• 在复杂情况下引入"安全路径"概念进行精细分析

这种"距离差+路径分析"的方法在追逐类图论问题中具有代表性，展示了如何将直观的博弈策略转化为可计算的图论性质。