luogu#P10039. [CCPC 2023 北京市赛] 游戏
[CCPC 2023 北京市赛] 游戏
题目描述
小 I 和小 J 又在玩游戏。
小 J 找来了一棵 个点的树。树上的每条边有开启和关闭两个状态,初始树上每条边都是开启的。
初始树上有一颗棋子放在 号节点。小 I 可以移动棋子,目标是将棋子移动到一个度数恰好为 的节点上;小 J 可以关闭树上的边,目标是阻止小 I 将棋子移动到度数恰好为 的节点上。
游戏分为若干轮,每轮有如下环节:
- 小 I 任务判定:如果棋子在度数恰好为 的节点上,小 I 获胜,否则进入第 2 步;
- 小 J 行动:小 J 将一条目前开启的边,将这条边永久关闭,进入第 3 步,如果目前不存在开启的边则直接跳过行动进入第 3 步;
- 小 I 行动:小 I 选择一条连接当前棋子所在节点且开启的边,将棋子移动到这条边的另一个节点上。如果没有这样的边,小 J 获胜,否则进入新的一轮,回到第 1 步。
小 J 想知道,如果小 I 和小 J 知道这棵树的形态且绝顶聪明,谁会获胜。
输入格式
第一行一个整数 表示树的节点数,接下来 行每行两个整数 ,表示树上的一条边。
输出格式
如果小 I 获胜,输出 You win, temporarily.
,否则输出 Wasted.
。
6
1 2
2 3
2 4
1 5
5 6
Wasted.
7
1 2
2 3
2 4
1 5
5 6
5 7
You win, temporarily.
提示
【样例解释 1】
小 J 的策略如下:
- 小 J 将 关闭,这样小 I 只能移动到 ;
- 小 J 将 关闭,这样小 I 只得移动回 ;
- 小 J 将 关闭,于是小 I 无法移动。