A6704. 「HEOI2013」Eden 的博弈树
编程题
提高+/省选-
知识点
题目描述
对于有两个玩家的，状态透明且状态转移确定的博弈游戏，博弈树是常用的分析工具。博弈树是一棵有根树，其中的节点为游戏的状态。若节点 $B$ 的父亲是 $A$，则说明状态 $A$ 能通过一次决策转移到状态 $B$。每个状态都有一个唯一的决策方，即这个状态下应该由哪一方做出决策。我们规定双方在任何时候都是轮流做出决策的，即树上相邻节点的决策方总是不相同的。
在这个问题中，我们只关心两个玩家的胜负情况，且规定游戏不会出现平局。
我们称两个玩家分别为黑方和白方，其中根节点的决策方为黑方。显然每个节点只有两个状态：黑方胜和白方胜。若某内节点（即存在后继节点的节点）的决策方为黑方，则该节点为黑方胜的充要条件为它的儿子中存在黑方胜的节点，反之亦然。求解博弈树即为判明博弈树根节点的状态。
如果我们得知了所有叶节点（即无后继节点的节点）的状态，那么博弈树就很容易求解了。但是现在的情况是所有叶节点的状态均为未知的，需要进一步的计算。对于一个由叶节点构成的集合 $S$，如果 $S$ 中的节点均被判明为黑方胜，就 可以断言根节点为黑方胜的话，则称 $S$ 为一个黑方胜集合。对于黑方胜集合 $S$， 如果对于任意的黑方胜集合 $S’$ 均满足 $|S| \leq |S’|$（$|S|$ 表示集合 $S$ 中的元素数目），则称 $S$ 为一个最小黑方胜集合。同样地，也可以定义白方胜集合和最小白方胜集合。
Eden 最近在研究博弈树问题。他发现，如果一个叶节点既属于某一个最小黑方胜集合，又属于一个最小白方胜集合，那么求解这个节点的状态显然最有益于求解根节点的状态。像这样的叶节点就称之为关键叶节点。对于一棵给定的博弈树，Eden 想要知道哪些叶节点是关键叶节点。
在这个问题中，我们只关心两个玩家的胜负情况，且规定游戏不会出现平局。
我们称两个玩家分别为黑方和白方，其中根节点的决策方为黑方。显然每个节点只有两个状态：黑方胜和白方胜。若某内节点（即存在后继节点的节点）的决策方为黑方，则该节点为黑方胜的充要条件为它的儿子中存在黑方胜的节点，反之亦然。求解博弈树即为判明博弈树根节点的状态。
如果我们得知了所有叶节点（即无后继节点的节点）的状态，那么博弈树就很容易求解了。但是现在的情况是所有叶节点的状态均为未知的，需要进一步的计算。对于一个由叶节点构成的集合 $S$，如果 $S$ 中的节点均被判明为黑方胜，就 可以断言根节点为黑方胜的话，则称 $S$ 为一个黑方胜集合。对于黑方胜集合 $S$， 如果对于任意的黑方胜集合 $S’$ 均满足 $|S| \leq |S’|$（$|S|$ 表示集合 $S$ 中的元素数目），则称 $S$ 为一个最小黑方胜集合。同样地，也可以定义白方胜集合和最小白方胜集合。
Eden 最近在研究博弈树问题。他发现，如果一个叶节点既属于某一个最小黑方胜集合，又属于一个最小白方胜集合，那么求解这个节点的状态显然最有益于求解根节点的状态。像这样的叶节点就称之为关键叶节点。对于一棵给定的博弈树，Eden 想要知道哪些叶节点是关键叶节点。
输入格式
第一行包含一个正整数 $n$，表示博弈树的节点数目。节点从 $1$ 到 $n$ 编号，且 $1$ 号节点为根节点。
之后 $n – 1$ 行，每行包含一个正整数。第 $i$ 行的正整数表示节点 $i$ 的父节点的编号。
之后 $n – 1$ 行，每行包含一个正整数。第 $i$ 行的正整数表示节点 $i$ 的父节点的编号。
输出格式
在一行内输出三个空格分隔的正整数，分别是编号最小的关键叶节点的编号，关键叶节点的数目和所有关键叶节点的编号的异或和。
输入输出样例
输入 #1
7 1 1 2 2 3 3
输出 #1
4 4 0
说明/提示
对于 $30\%$ 的数据，$n \leq 100$；
对于 $40\%$ 的数据，$n \leq 1000$；
对于 $50\%$ 的数据，$n \leq 10000$，且树是随机生成的；
对于 $100\%$ 的数据，$1 \leq n \leq 200000$，且对于节点 $i$（$i \ne 1$），其父节点的编号小于
$i$。
对于 $40\%$ 的数据，$n \leq 1000$；
对于 $50\%$ 的数据，$n \leq 10000$，且树是随机生成的；
对于 $100\%$ 的数据，$1 \leq n \leq 200000$，且对于节点 $i$（$i \ne 1$），其父节点的编号小于
$i$。