luogu#P10039. [CCPC 2023 北京市赛] 游戏

[CCPC 2023 北京市赛] 游戏

题目描述

小 I 和小 J 又在玩游戏。

小 J 找来了一棵 nn 个点的树。树上的每条边有开启和关闭两个状态,初始树上每条边都是开启的。

初始树上有一颗棋子放在 11 号节点。小 I 可以移动棋子,目标是将棋子移动到一个度数恰好11 的节点上;小 J 可以关闭树上的边,目标是阻止小 I 将棋子移动到度数恰好为 11 的节点上。

游戏分为若干轮,每轮有如下环节:

  1. 小 I 任务判定:如果棋子在度数恰好为 11 的节点上,小 I 获胜,否则进入第 2 步;
  2. 小 J 行动:小 J 将一条目前开启的边,将这条边永久关闭,进入第 3 步,如果目前不存在开启的边则直接跳过行动进入第 3 步;
  3. 小 I 行动:小 I 选择一条连接当前棋子所在节点且开启的边,将棋子移动到这条边的另一个节点上。如果没有这样的边,小 J 获胜,否则进入新的一轮,回到第 1 步。

小 J 想知道,如果小 I 和小 J 知道这棵树的形态且绝顶聪明,谁会获胜。

输入格式

第一行一个整数 n(1n105)n (1 \le n \le 10^5) 表示树的节点数,接下来 n1n-1 行每行两个整数 u,v(1u,vn)u,v (1 \le u, v \le n),表示树上的一条边。

输出格式

如果小 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 将 (1,2)(1,2) 关闭,这样小 I 只能移动到 55
  • 小 J 将 (5,6)(5,6) 关闭,这样小 I 只得移动回 11
  • 小 J 将 (1,5)(1,5) 关闭,于是小 I 无法移动。