결정 트리 (라지)

결정 트리, 그중에서도 분류 트리라고 부르는 종류는 항목의 특징을 읽어 항목을 범주로 나누는 자료구조다. 예를 들어 어떤 동물은 귀엽고 어떤 동물은 귀엽지 않다. 주어진 동물이 귀여운지는 아래 트리를 따라 내려가면서 판정한다.

(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는 각각 토큰이다. 두 토큰 사이에는 공백 문자가 최소 하나 들어가지만, 여는 괄호 ( 바로 뒤와 닫는 괄호 ) 바로 앞에서는 공백이 없을 수도 있다. 공백 문자는 space ' '와 개행 '\n'이다.

동물이 귀여울 확률은 이렇게 구한다. 루트에서 $p = 1$로 시작한다. 각 노드에서 $p$에 그 노드의 가중치를 곱한다. 노드가 부분 트리를 갖지 않는 잎이면 멈추고, 그때의 $p$가 그 동물이 귀여울 확률이다. 잎이 아니면 노드에 저장된 특징을 본다. 동물이 그 특징을 가지고 있으면 첫 번째 부분 트리로 내려가고, 없으면 두 번째 부분 트리로 내려가서 같은 과정을 반복한다.

예를 들어 비버는 furry와 freshwater, 두 특징이 있다. 루트에서 $p = 1$로 시작해 루트의 가중치 0.2를 곱한다. 비버는 털이 있으니 첫 번째 부분 트리로 내려가 0.81을 곱하고, $p$는 0.162가 된다. 비버는 빠르지 않으니 두 번째 부분 트리로 내려가 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 100$
• $0 \le n \le 100$

각 테스트 케이스마다 먼저 Case #x:를 한 줄에 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호다. 그 다음 정확히 $A$개의 줄에 입력과 같은 순서로 동물 하나씩의 답을 출력한다.

각 줄에는 그 동물이 귀여울 확률을 소수점 아래 7자리로 정확히 맞춰 출력한다. 그 자리에서 가장 가까운 값으로 반올림하고, 정확히 중간인 값은 올린다. 정수부는 항상 0 또는 1이므로 확률 1은 1.0000000으로 출력한다.