#P17521. PM12786黑白树博弈

PM12786黑白树博弈

题目描述

给定一棵以 00 号节点为根的有根树,每个节点初始被染成黑色或白色。

Masha 和 Petya 在树上进行博弈,Masha 先手。轮到某位玩家时,他必须选择一个当前为白色的节点 uu,并可以任意选择 uu 的若干后代节点(可以不选,也不要求连通)。随后,将被选中的所有节点以及节点 uu 的颜色全部取反:黑变白,白变黑。

如果某位玩家轮到行动时不存在任何白色节点,则该玩家失败。

假设双方均采用最优策略,判断谁会获胜。

输入格式

第一行输入一个整数 N−1N-1,表示父亲数组的长度。

第二行输入 N−1N-1 个整数 p0,p1,…,pN−2p_0,p_1,\ldots,p_{N-2}。对于每个 0≤i<N−10\le i<N-1,节点 i+1i+1 的父亲为 pip_i。

第三行输入一个长度为 NN 的字符串 color:字符 W 表示白色,B 表示黑色。

输出格式

如果 Masha 必胜,输出 Masha;否则输出 Petya。

数据范围

  • 2≤N≤502\le N\le 50;
  • 0≤pi<N0\le p_i<N;
  • 输入保证这些边构成一棵以 00 为根的树。