GameInDarknessDiv1

作者：洪华敦

关键词：博弈

题目简述

以网格图的形式给你一棵树，Alice 和 Bob 在树上博弈，一开始双方都知道对方的初始位置。

每轮开始时有 Alice 先走，移动到相邻的结点上，然后 Bob 也移动到一个相邻的结点，注意不能在原地不动。

当某个人移动完后如果两人在同一结点 Alice 胜。在很多步内 Alice 无法抓到 Bob 的话，Bob胜。

你需要计算 Alice是否存在一条移动路径，使得在 Bob 知道 Alice 的移动路径的情况下仍然必败。

数据范围

1<=n，m<=50

题解

这是一个结论题，先说结论：当存在一个点 P ，满足 dis(A,P)>=dis(B,P)+2，且以 P 为根时有至少 3 个子树的深度大于等于 3 时，Bob 胜，否则 Alice 胜。

充分性证明

Bob可以先走到点 P，这时 Alice 距离点 P 至少是 2。

之后 Alice 的决策肯定是走到点 P，然后逐一检查每个子树。

我们定义浅检查为往该子树走一格后直接回到 P，深检查为往该子树里走至少 2 格。

Bob 可以躲在某个子树的深度为 2 的点上，由于 Bob 知道 Alice 的计划，Bob可以选择躲在不是第一个深检查的子树里。

当 Alice 进行第一次深检查时，Bob 可以跑到 P 上，然后在剩下两个子树里再选一个躲避下一次深检查。

如果 Alice 浅检查的话，Bob 往下走一格然后走回来即可。

于是 Bob 必胜。

必要性证明

我们定义一个结点 P 是分支点，当且仅当dis(A,P)>=dis(B,P)+2，且去掉 P 后至少有 3 个子连通分量。

Alice 的策略是无脑往 Bob 那边走，直到碰到第一个分支点 P。

因为 Bob 提早 2 个单位时间到达 P，所以现在 Bob 可能在 P 的某一个子连通分量里。

由于 P 是第一个分支点，所以 Bob 不可能在 A 的起始点的那个子连通分量里。

情况1：只有一个子连通分量深度大于等于 3

这种情况很简单，对于深度小于等于 2 的子树，浅检查就能排除嫌疑。

于是递归着往那个深度大于等于 3 的子连通分量里走就好了，注意由于 P 是分支点，所以那个子连通分量里所有度数 大于等于 3 的都是分支点。

情况2：有两个子连通分量深度大于等于 3

往一个子连通分量里走，每次碰到深度小于等于 2 的子树就浅检查一下，因为最多只有一个深度大于等于 3 的子连通分量，一直往那个走就行了，然后走回来一样。

这样这个子连通分量里就一定没有 Bob 了，转情况1

时间复杂度 $O(nm)$