题解：P14760 [Opoi 2025] CCD 的游戏

SuyctidohanQ · 2025-12-16 19:28:08 · 题解

考虑树形 DP。设 f_x 表示在以 x 为根的子树中，当 x 未被标记时，先手是否有必胜策略（f_x = 1 表示先手必胜，f_x = 0 表示后手必胜）。

对于叶子节点 x，显然 f_x = 1，因为先手标记 x 后游戏结束，后手无法操作。

对于非叶子节点 x，考虑其所有子节点 y。如果存在某个子节点 y 满足 f_y = 1，那么 f_x = 0；否则 f_x = 1。这是因为：

• 如果存在 f_y = 1，那么后手可以在 x 被标记后，选择标记那个子树，从而获得必胜局面。
• 如果所有 f_y = 0，那么无论后手选择标记哪个子树，先手都能在下一轮获得必胜局面。

注意：由于 1 号节点初始已被标记，因此实际游戏中从 1 的子节点开始。相当于 1 号节点被标记后，轮到后手操作。所以如果 f_1 = 1，说明在原游戏中（从 1 开始）后手必胜，输出 second；如果 f_1 = 0，则先手必胜，输出 first。