Optimal alpha beta pruning
Fox Ciel is developing an artificial intelligence (AI) for a game. This game is described as a game tree T with nvertices. Each node in the game has an evaluation value which shows how good a situation is. This value is the same as maximum value of child nodes’ values multiplied by -1. Values on leaf nodes are evaluated with Ciel’s special function - which is a bit heavy. So, she will use alpha-beta pruning for getting root node’s evaluation value to decrease the number of leaf nodes to be calculated.
By the way, changing evaluation order of child nodes affects the number of calculation on the leaf nodes. Therefore, Ciel wants to know the minimum and maximum number of times to calculate in leaf nodes when she could evaluate child node in arbitrary order. She asked you to calculate minimum evaluation number of times and maximum evaluation number of times in leaf nodes.
Ciel uses following algotithm:
function negamax(node, α, β)
if node is a terminal node
return value of leaf node
else
foreach child of node
val := -negamax(child, -β, -α)
if val >= β
return val
if val > α
α := val
return α
Input
Input follows following format:
n
p_1 p_2 ... p_n
k_1 t_11 t_12 ... t_1k
...
k_n t_n1 t_n2 ... t_nk
The first line contains an integer n, which means the number of vertices in game tree T.
The second line contains n integers p_i, which means the evaluation value of vertex i.
Then, next n lines which contain the information of game tree T.
k_i is the number of child nodes of vertex i, and t_ij is the indices of the child node of vertex i.
Input follows following constraints:
2 ≤ n ≤ 100
−10000 ≤ p_i ≤ 10000
0 ≤ k_i ≤ 5
2 ≤ t_ij ≤ n
Index of root node is 1.
Evaluation value except leaf node is always 0. This does not mean the evaluation values of non-leaf nodes are 0. You have to calculate them if necessary.
Leaf node sometimes have evaluation value of 0.
Game tree T is tree structure.
Output
Print the minimum evaluation number of times and the maximum evaluation number of times in leaf node.
Please separated by whitespace between minimum and maximum.