결정 트리 | cho.sh

문제

결정 트리, 그중에서도 분류 트리는 항목의 특징을 보고 그 항목을 범주로 나누는 자료구조다. 예를 들어 동물은 귀엽거나 귀엽지 않다고 하자. 동물 하나가 주어지면 그 동물의 특징을 보고 아래 결정 트리로 귀여운지 판단한다.

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

결정 트리는 재귀적으로 정의된다. 결정 트리에는 항상 루트 노드와 가중치가 있다. 여기에 특징 이름과 두 개의 부분 트리가 더 붙기도 하고, 두 부분 트리도 각각 결정 트리다.

형식으로 쓰면 다음 문법을 따른다.

tree ::= (weight [feature tree tree])
weight는 0 이상 1 이하의 실수
feature는 길이가 1 이상인 영어 소문자 문자열

대괄호 [] 안쪽은 생략할 수 있다. 괄호 (와 ), weight, feature는 모두 토큰이다. 두 토큰 사이에는 공백 문자가 적어도 하나 들어간다. 단 여는 괄호 바로 뒤와 닫는 괄호 바로 앞에는 공백이 없어도 된다. 공백 문자는 띄어쓰기와 개행이다.

동물이 귀여울 확률을 구하려면 $p$ 를 1로 두고 트리의 루트에서 시작한다. 각 노드에서 $p$ 에 그 노드의 가중치를 곱한다. 그 노드가 리프이면, 즉 부분 트리가 없으면 거기서 멈추고 그때의 $p$ 가 이 동물이 귀여울 확률이다. 리프가 아니면 노드에 붙은 특징을 확인한다. 동물에게 그 특징이 있으면 첫 번째 부분 트리로 내려가 같은 과정을 반복하고, 없으면 두 번째 부분 트리로 내려가 반복한다.

예를 들어 비버는 furry와 freshwater 두 특징이 있다. $p$ 를 1로 두고 루트에서 시작해 루트의 가중치 0.2를 곱한다. 비버는 furry이므로 첫 번째 부분 트리로 내려가 0.81을 곱하고, $p$ 는 0.162가 된다. 비버는 fast가 아니므로 거기서 두 번째 부분 트리로 내려간다. 마지막으로 0.2를 곱해 0.0324를 얻는다. 이것이 비버가 귀여울 확률이다.

결정 트리 하나와 특징이 적힌 동물 목록이 주어진다. 동물마다 귀여울 확률을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $N$ 이 주어진다. 이어서 $N$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 결정 트리를 적는 데 쓴 줄 수 $L$ 이 주어진다. 다음 $L$ 개의 줄에 위 형식으로 결정 트리가 주어진다. 그 다음 줄에는 동물의 수 $A$ 가 주어진다. 이어지는 $A$ 개의 줄에 동물 하나의 정보가 다음 형식으로 주어진다.

animal n feature1 feature2 ... featuren

제한

$1 \le N \le 100$
모든 가중치는 0 이상 1 이하다.
가중치는 숫자와 소수점 한 개까지로만 이루어진다.
가중치는 소수점으로 시작하지 않고 소수점으로 끝나지도 않는다.
가중치의 소수점 앞에 0이 두 개 이상 오지 않는다.
모든 동물 이름과 특징 이름은 길이가 1 이상 10 이하인 영어 소문자 문자열이다.
한 테스트 케이스 안의 동물 이름은 서로 다르다.
한 동물의 특징 이름은 서로 다르다.
결정 트리를 적은 $L$ 개의 줄은 개행을 빼고 각각 80자 이하다.
$1 \le L \le 100$
$1 \le A \le 10$
$0 \le n \le 5$

출력

각 테스트 케이스마다 먼저 Case #x: 형식으로 한 줄을 출력한다. 여기서 $x$ 는 1부터 시작하는 테스트 케이스 번호다. 그 다음 정확히 $A$ 개의 줄을 입력에 주어진 순서대로 출력하고, 각 줄에는 그 동물이 귀여울 확률을 소수점 아래 일곱째 자리까지 반올림해 적는다.

소수점 아래 자릿수는 항상 일곱 자리로 채운다. 예를 들어 0.0324000, 1.0000000처럼 쓴다. 반올림은 다섯일 때 올리는 방향으로 하며, 정답이 소수점 아래 일곱째 자리 기준으로 정확히 중간값이 되는 경우는 입력에 없다.