최적의 알파-베타 가지치기

Ciel 여우는 어떤 게임을 위한 인공지능을 만들고 있다. 이 게임은 정점이 $n$개인 게임 트리 $T$로 표현된다. 각 노드는 상황이 얼마나 좋은지를 나타내는 평가값을 가진다. 리프가 아닌 노드의 값은 자식 노드들 값의 최댓값에 $-1$을 곱한 것이다. 리프의 값은 계산 비용이 큰 Ciel의 특수한 함수로 구한다. 그래서 Ciel은 알파-베타 가지치기로 루트의 평가값을 구하면서, 계산하는 리프 노드 수를 줄인다.

자식 노드를 평가하는 순서에 따라 리프 노드를 계산하는 횟수가 달라진다. Ciel은 각 노드의 자식을 임의의 순서로 평가할 수 있을 때, 리프 계산 횟수의 최솟값과 최댓값을 알고 싶어 한다. Ciel이 사용하는 알고리즘은 다음과 같다.

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 α

negamax algorithm

첫 줄에 게임 트리의 정점 수 $n$이 주어진다. 둘째 줄에는 각 정점 $i$의 평가값 $p_i$가 $n$개 주어진다. 이어지는 $n$개의 줄에 트리 정보가 주어지며, $k_i$는 정점 $i$의 자식 수이고, 뒤이어 자식의 번호 $t_{ij}$가 나온다.

n
p1 p2 ... pn
k1 t11 t12 ... t1k
:
:
kn tn1 tn2 ... tnk

• $2 \le n \le 100$
• $-10000 \le p_i \le 10000$
• $0 \le k_i \le 5$
• $2 \le t_{ij} \le n$
• 루트의 번호는 $1$이다.
• 입력에서 리프가 아닌 노드의 평가값은 항상 $0$이다. 필요하면 직접 계산한다.
• 리프의 평가값이 $0$인 경우도 있다.
• 게임 트리는 트리 구조이다.

리프 계산 횟수의 최솟값과 최댓값을 공백으로 구분하여 출력한다.

minimum maximum