QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 256 MB 總分: 100

#4589. 黑白树

统计

“White-Black Tree” 是一个在有根树上进行的双人游戏,树共有 $N$ 个节点。节点编号从 $1$ 到 $N$,其中节点 $1$ 为根节点。树中每个节点都有一个颜色 $C_i$,取值为 $0$(代表黑色)或 $1$(代表白色),颜色可以根据游戏规则进行改变。

两位对手轮流进行游戏。在每一轮中,玩家选择树中的一个白色节点,设该节点为 $x$。首先,节点 $x$ 的颜色 $C_x$ 从白色变为黑色。然后,在同一轮中,玩家可以改变 $x$ 的任意数量的后代节点的颜色(从白色变为黑色,或从黑色变为白色)。如果节点 $y$ 的父节点是 $x$ 或者 $x$ 的后代,则称 $y$ 是 $x$ 的后代。无法进行任何移动的玩家输掉游戏,另一方获胜。

你的任务是判断在双方均采取最优策略的情况下,谁将赢得游戏;这意味着如果存在一种能保证获胜的移动,玩家一定会采取该移动。

例如,考虑一个 $N = 7$ 的有根树,初始颜色为 $C_{1..7} = \{0, 1, 1, 0, 0, 0, 1\}$。

此时有三个白色节点(节点 $2, 3, 7$),先手玩家可以选择其中之一作为第一步。在这个例子中,先手玩家存在获胜策略。一种最优策略是选择节点 $3$,将 $C_3$ 变为 $0$(黑色),然后改变节点 $6$ 和节点 $7$(均为节点 $3$ 的后代)的颜色,即 $C_6$ 变为 $1$(白色),$C_7$ 变为 $0$(黑色)。轮到后手玩家时,只剩下两个白色节点可选(节点 $2$ 和 $6$),且它们都没有后代。无论后手玩家如何选择,先手玩家只需选择剩下的那个白色节点,使得后手玩家无法再进行任何移动。因此,后手玩家输掉游戏,先手玩家赢得该局。

输入格式

输入第一行包含一个整数 $N$ ($2 \le N \le 100\,000$),表示给定树的节点数。 第二行包含 $N - 1$ 个整数 $P_i$ ($1 \le P_i < i$),对于 $i = 2..N$,表示节点 $i$ 的父节点。 第三行包含 $N$ 个整数 $C_i$ ($C_i \in \{0, 1\}$),表示节点 $i$ 的初始颜色。整数 $0$ 代表黑色,整数 $1$ 代表白色。

输出格式

如果先手玩家在双方均采取最优策略的情况下获胜,输出字符串 "First";否则,输出字符串 "Second"。

样例

输入格式 1

7
1 1 1 3 3 3
0 1 1 0 0 0 1

输出格式 1

First

说明

这是题目描述中的例子。

输入格式 2

5
1 1 2 3
0 1 1 0 0

输出格式 2

Second

说明

黑色的根节点有两个白色的子节点,且这两个子树的结构和颜色完全相同。无论先手玩家在其中一个子树上做什么操作,后手玩家只需在另一个子树上进行相同的操作即可。

输入格式 3

4
1 1 1
1 1 0 1

输出格式 3

First

说明

先手玩家可以通过选择节点 $1$,在一步之内将所有节点变为黑色。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.