#P15613. [ICPC 2021 Jakarta R] White-Black Tree

[ICPC 2021 Jakarta R] White-Black Tree

说明

黑白树是一款双人游戏,在一棵有根树上进行,树有 NN 个节点。节点编号从 11NN,节点 11 是根。树中每个节点都有一个颜色 CiC_{i},取值为 00(代表黑色)或 11(代表白色),可以根据游戏规则进行改变。

两名对手轮流行动。轮到某位玩家时,他需要选择一个树中的 白色 节点;设所选节点为 xx。首先,节点 xx 的颜色 CxC_{x} 由白色变为黑色。然后,在同一回合中,玩家可以改变节点 xx 的后代节点中零个或多个节点的颜色,可以将白色变为黑色,也可以将黑色变为白色。节点 yy 是节点 xx 的后代当且仅当节点 yy 的父节点是节点 xx 或者是节点 xx 的后代。无法进行任何操作的玩家输掉游戏,另一方获胜。

你的任务是确定在双方都采取最优策略的情况下谁将获胜;这意味着如果存在能保证获胜的移动,他们一定会选择那样的移动。

例如,考虑下面一个有 N=7N = 7 个节点的有根树,初始颜色为 C1..7={0,1,1,0,0,0,1}C_{1..7} = \{0, 1, 1, 0, 0, 0, 1\}

:::align{center} :::

有三个白色节点(节点 223377),先手玩家可以在第一步选择它们。在此例中,先手玩家有获胜策略。先手玩家的一种最优玩法是选择节点 33,将 C3C_{3} 变为 00(黑色),然后将节点 66 和节点 77(都是节点 33 的后代)的颜色翻转,即 C6C_{6} 变为 11(白色),C7C_{7} 变为 00(黑色)。轮到后手玩家时,只剩下两个白色节点(节点 2266)可供选择,且它们都没有任何后代。无论后手玩家选择哪个,先手玩家只需选择剩下的那个白色节点,使得后手玩家无法再进行任何操作。因此后手玩家输掉游戏,先手玩家获胜。

输入格式

输入第一行包含一个整数 NN2N1000002 \leq N \leq 100\,000),表示给定树的节点数量。第二行包含 N1N-1 个整数 PiP_{i}1Pi<i1 \leq P_{i} < i),其中 i=2..Ni = 2..N,表示节点 ii 的父节点。第三行包含 NN 个整数 CiC_{i}Ci{0,1}C_{i} \in \{0, 1\}),表示节点 ii 的初始颜色。颜色黑色用整数 00 表示,白色用整数 11 表示。

输出格式

如果双方都采取最优策略,先手玩家将获胜,则输出一行字符串 "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 解释

先手玩家可以通过选择节点 11,在一回合内将所有节点变为黑色。

翻译由 DeepSeek 完成