#P15613. [ICPC 2021 Jakarta R] White-Black Tree
[ICPC 2021 Jakarta R] White-Black Tree
说明
黑白树是一款双人游戏,在一棵有根树上进行,树有 个节点。节点编号从 到 ,节点 是根。树中每个节点都有一个颜色 ,取值为 (代表黑色)或 (代表白色),可以根据游戏规则进行改变。
两名对手轮流行动。轮到某位玩家时,他需要选择一个树中的 白色 节点;设所选节点为 。首先,节点 的颜色 由白色变为黑色。然后,在同一回合中,玩家可以改变节点 的后代节点中零个或多个节点的颜色,可以将白色变为黑色,也可以将黑色变为白色。节点 是节点 的后代当且仅当节点 的父节点是节点 或者是节点 的后代。无法进行任何操作的玩家输掉游戏,另一方获胜。
你的任务是确定在双方都采取最优策略的情况下谁将获胜;这意味着如果存在能保证获胜的移动,他们一定会选择那样的移动。
例如,考虑下面一个有 个节点的有根树,初始颜色为 。
:::align{center}
:::
有三个白色节点(节点 、 和 ),先手玩家可以在第一步选择它们。在此例中,先手玩家有获胜策略。先手玩家的一种最优玩法是选择节点 ,将 变为 (黑色),然后将节点 和节点 (都是节点 的后代)的颜色翻转,即 变为 (白色), 变为 (黑色)。轮到后手玩家时,只剩下两个白色节点(节点 和 )可供选择,且它们都没有任何后代。无论后手玩家选择哪个,先手玩家只需选择剩下的那个白色节点,使得后手玩家无法再进行任何操作。因此后手玩家输掉游戏,先手玩家获胜。
输入格式
输入第一行包含一个整数 (),表示给定树的节点数量。第二行包含 个整数 (),其中 ,表示节点 的父节点。第三行包含 个整数 (),表示节点 的初始颜色。颜色黑色用整数 表示,白色用整数 表示。
输出格式
如果双方都采取最优策略,先手玩家将获胜,则输出一行字符串 "First"。否则输出一行字符串 "Second"。
7
1 1 1 3 3 3
0 1 1 0 0 0 1
First
5
1 1 2 3
0 1 1 0 0
Second
4
1 1 1
1 1 0 1
First
提示
样例 #2 解释
黑色根节点有两个白色子节点,它们具有相同的子树结构和颜色。无论先手玩家对一个子节点做什么操作,后手玩家只需在另一个子节点上模仿即可。
样例 #3 解释
先手玩家可以通过选择节点 ,在一回合内将所有节点变为黑色。
翻译由 DeepSeek 完成
京公网安备 11011102002149号