配点: 100 点
黑兔:「带根的树就是带根的树的多重集吧」
白兔:「?」
黑兔:「顺便说一下,有这样一个游戏」
白兔:「这是什么,会结束吗?」
黑兔:「在结束之前可能就会用完纸」
問題文
带根树对于『带根树的多重集合,通过用新的 1 个顶点和边将它们的根连接,并以该顶点作为根』来递归定义(注意连接顺序不区分)。 特别是,1 仅由顶点组成的树对应空集合。本问题中,仅考虑顶点数有限的带根树。 带根树 T_1, \ldots, T_k 连接到新的根的带根树记作 \{\!\!\{T_1, \ldots, T_k\}\!\!\} 。 例如如下图所示。
带根树是带根树多重集合
带根树 T, T' 的顺序,当T_1 \ge \cdots \ge T_k,\, T'_1 \ge \cdots \ge T'_l 通过 T = \{\!\!\{T_1, \ldots, T_k\}\!\!\},\, T' = \{\!\!\{T'_1, \ldots, T'_l\}\!\!\} 表示时, 列 s = (T_1, \ldots, T_k),\, s' = (T'_1, \ldots, T'_l) 按字典顺序比较, s < s' 如果 T < T',s = s' 如果 T = T',s > s' 如果 T > T'"作为递归定义(表示T \ge T' 是 您也可以写 T > T' 或 至少 T = T' )。 例如,如下图所示。
有根树的顺序
黑兔和白兔进行游戏。 棋盘上有几棵有根树。 最初,当顶点总数为 N 可用, 它的编号为1 减去 N 。 P_i = 0 时,顶点 i 是在棋盘上的有根树中 1 个根,并且P_i > 0 时,顶点 i 和 边缘 P_i 通过边连接。先手黑兔和后手白兔轮流进行以下操作:在棋盘上选取 1 个带根的树,并按上面规定的顺序将其改写为严格小于它的带根树(也就是说,选取的带根树被 T 当T > T' 带根的树木 T' 该值应乘以 1 选择若干个,将选择的部分 T' 改变为)。 不能行动的一方为负,若对方负则为胜。
黑兔和白兔都遵守以下规定。
- 如果一定能赢,就采取赢的方法行动。
- 虽然不一定能赢,但如果可以确保不输,就采取不输的方法行动。
此时决定谁会赢,或者游戏是否会无限进行。
制約
- 1 \le N \le 201912.
- 0 \le P_i \le i - 1 (1 \le i \le N).
部分点
- N \le 2019 的数据集,45 点。 如果所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 55 点。 如果所有满足
入力
N P_1 ... P_N
出力
如果黑兔获胜 Black 如果白兔获胜 White 如果游戏无限进行 Infinity 。
入力例 1
8 0 0 0 1 2 2 3 7
出力例 1
Black
黑兔在第一手将顶点 3 重写为以根为根的子树,如图所示,就能获胜。
入力例 1
入力例 2
14 0 1 2 2 1 5 5 0 8 8 10 10 9 9
出力例 2
White