CF1404B. Tree Tag

1405D - 树标记

让我们独立地考虑几个情况。

情况1：$ \text{dist}(a, b) \leq da $

不出所料，在这种情况下，Alice 在第一步就通过标记 Bob 获胜。

情况2：$ 2da \geq \text{树的直径} $

在这里，树的直径被定义为最长简单路径的长度。

在这种情况下，Alice 可以移动到树的中心。一旦 Alice 在那里，无论 Bob 在哪里，Alice 都可以在树中只用一步到达任何顶点，从而赢得比赛。

情况3：$ db > 2da $

在这种情况下，让我们描述一个 Bob 获胜的策略。因为我们不在情况1中，Bob 在他的第一步之前不会输掉比赛。那么，足以证明 Bob 总是可以在与 Alice 的距离大于 $ da $ 的情况下结束他的回合。

由于我们不在情况2中，至少有一个与 Alice 距离至少为 $ da $ 的顶点。如果 Bob 在他回合开始时位于这样的顶点，他应该简单地留在那里。否则，有某个顶点 $ v $ 满足 $ \text{dist}(a, v) = da + 1 $。那么 $ \text{dist}(b, v) \leq \text{dist}(b, a) + \text{dist}(a, v) \leq da + (da + 1) = 2da + 1 \leq db $，所以 Bob 可以在他的回合中跳到 $ v $。

情况4：$ db \leq 2da $

在这种情况下，Alice 的策略将是尽可能捕捉 Bob 或者移动一个顶点以靠近 Bob。让我们证明 Alice 将在有限的移动次数内获胜。

让我们将树的根设为 $ a $。Bob 位于 $ a $ 的某个子树中，假设有 $ k $ 个顶点。Alice 每次移动一个顶点，减少 Bob 的子树大小至少一个顶点。由于 $ db \leq 2da $，Bob 不能移动到另一个子树而不被立即捕获，所以 Bob 必须留在这个不断缩小的子树中，直到他不可避免地被击败。

解决方案

实现中唯一非平凡的部分是检查情况1和2。情况1 只需通过 DFS 检查。情况2 只需计算树的直径，这是一个标准问题。

复杂度是 $ O(n) $。