P5801 [SEERC 2019] Game on a Tree

Alice 和 Bob 在树上玩游戏。最初的时候，树上的所有节点都是白色的。 Alice 先手，她可以任选一个节点并在该点上放置一个标记，该点变为黑色。在这之后，玩家轮流进行游戏，每一回合中玩家可以将标记从所在点移动到该点的白色祖先节点或儿子节点中，并将移动到的点变为黑色。无法进行移动的玩家即输。 谁会赢得游戏呢？ 在有根树上，节点 $v$ 的*祖先节点*是指从树根到节点 $v$ 的路径上的任意点。 在有根树上，节点 $v$ 的*儿子节点*是指满足节点 $v$ 在从树根到节点 $w$ 路径上的任意点 $w$。 规定树的树根为点 $1$。

无

无

第一组样例中，树的形态是 $4$ 个点的一条链，所以 Bob 总是可以把标记移到最后的白点上。 第二组样例中，Alice 的最佳策略是先把标记放在点 $3$ 上，然后 $3$ 会变为黑色。Bob 只能移动标记到点 $1$ 上。Alice 可以选择点 $4, 5, 6$ 或 $7$ 来移动。Bob 只能选择 $2$。Alice 选择 $2$ 的任一白色子节点，Bob 就无法移动了。